ما هو فرز مجموعات Java.Sort (العقد)؟

Question

أعتقد أنه مدمج، وهو O (N Log N).

ومع ذلك، لا يختلف الإخراج التالي:

-1,0000000099000391,0000000099000427
1,0000000099000427,0000000099000346
5,0000000099000391,0000000099000346
1,0000000099000427,0000000099000345
5,0000000099000391,0000000099000345
1,0000000099000346,0000000099000345

أنا فرز Nodelist من 4 عقود عن طريق رقم التسلسل، والفرز يفعل 6 مقارنات. أنا في حيرة لأن 6> (4 سجل (4)). يمكن للشخص أن يفسر هذا لي؟

ملاحظة: إنها مدمجة، لكن ما زلت لا أفهم نتائجي.

شكرا لأجوبتكم جميعا. شكرا لك توم لتصحيح الرياضيات بلدي.

Answer 1

O (N Log N) لا يعني أن عدد المقارنات سيكون مساويا أو أقل من سجل n، فقط أن الوقت المستغرق سوف مقياس بالتناسب إلى n سجل ن. حاول القيام باختبارات مع 8 عقدة، أو 16 عقد، أو 32 عقد، والتحقق من التوقيت.

Answer 2

قمت بفرز أربع العقد، لذلك لم تحصل على دمج فرز؛ فرز تبديل إلى نوع الإدراج.

في Java، تستخدم الأساليب () الأساليب دمج الترتيب أو QuickSorts ضبطها وفقا لقوات البيانات وكفاءة التنفيذ قم بالتبديل إلى الترتيب الإدراج عندما يتم فرز أقل من سبعة عناصر صفيف. (ويكيبيديا، وأضاف التركيز)

يتم استخدام Arrays.Sort بشكل غير مباشر من فئات المجموعات.

يشير تقرير الأخطاء المقبول مؤخرا إلى أن تنفيذ أشعة الشمس ل Java سيستخدم بيثون Timsort. فى المستقبل: http://bugs.sun.com/bugdatabase/view_bug.do؟bug_id=6804124.

(أولاد تيمسورت، المرتبطة أعلاه، يستحق القراءة.)

Answer 3

خوارزمية A (N) التي تعالج كمية من البيانات N موجودة في O (F (n))، بالنسبة لبعض الوظائف F، إذا كان هناك ثوابت إيجابية بدقة C_INF و C_SUP بحيث:

c_inf. f (n) <confectionValue (تشغيلي (} (n))) <c_sup. F (ن)

شيئين يجب ملاحظته:

• الثوابت الفعلية C يمكن أن يكون أي شيء، و فعل تعتمد على التكاليف النسبية للعمليات (اعتمادا على اللغة أو VM أو الهندسة المعمارية أو التعريف الفعلي لعملية). على بعض المنصات، على سبيل المثال، + و * لديها نفس التكلفة، على بعض الآخر في وقت لاحق هو ترتيب أبطأ الحجم.

• الكمية المنسوبة باسم "في O (f (n))" هي متوقع عدد عمليات التشغيل، بناء على بعض النموذج التعسفي المحتمل للبيانات التي تتعامل معها. على سبيل المثال، إذا تم فرز بياناتك بالكامل تقريبا، فإن خوارزمية فرز الدمج ستكون في الغالب (n)، وليس O (n. سجل (n)).

Answer 4

لقد كتبت بعض الأشياء التي قد تكون مهتما بها حول خوارزمية فرز Java وتأخذها بعض قياسات الأداء في المجموعات.. وبعد الخوارزمية في الوقت الحاضر Mergesort مع نوع الإدراج بمجرد النزول إلى حجم معين من الأساس (NB هذه الخوارزمية من المحتمل جدا أن تتغير في Java 7).

يجب أن تأخذ الرموز الكبيرة حقا كإشارة إلى كيفية قياس الخوارزمية بشكل عام؛ للحصول على نوع معين، سوف ينحرف الوقت الدقيق من الوقت الذي توقعه هذا الحساب (كما سترى على الرسم البياني الخاص بي، فإن خوارزميات الفرز التي يتم دمجها لكل منها خصائص أداء مختلفة، وبالتالي فإن الوقت الكلي للفرز هو أكثر تعقيدا أكثر تعقيدا).

ومع ذلك، كدليل تقريبي، في كل مرة تقوم فيها بتضاعف عدد العناصر، إذا مضتأ الوقت المتوقع بمقدار 2.2، فلن تكون بعيدا. (لا معنى لها حقا القيام بذلك للحصول على قوائم صغيرة جدا ببعض العناصر، رغم ذلك.)