النوع الوظيفي الفعال

Question

أنا أقوم ببرمجة وظيفة لـ ti-nspire, ، لذلك لا يمكنني استخدام المدمج من داخل وظيفة. ما هي الخوارزمية الأكثر فعالية بشكل عام لفرز قائمة بالأرقام دون تعديل القائمة نفسها؟ (عودية وتقسيم القائمة هي لعبة عادلة ، وكذلك الاستخدام العام للرياضيات.)

Answer 1

Mergesort واضحة وبسيطة وفعالة ومستقرة: تقسيم القائمة ، فرز متكرر ، ودمج النتائج.

لكي تكون أكثر تحديداً ، يأخذ Mergesort O (n log n) ، وهو الأمثل بشكل غير متمرس. أيضًا ، في الممارسة العملية (مع تعديل كل من الخوارزميات لفرز القالات الفرعية القصيرة باستخدام نوع من الأغراض الخاصة) ، يمكن أن يكون Mergesort منافسًا وثيقًا للرسائل السريعة المعدلة المستخدمة في المكتبات القياسية C/C ++.

تحرير: على عكس الأنواع الموجودة في مكانها مثل Quicksort و Sorted Tort ، يتطلب Mergesort ذاكرة مساعدة ، وهو أبسط للتنفيذ عن طريق النسخ بدلاً من التبديل.

Answer 2

تيمسورت يستخدم في Python و Java SE 7. يأخذ أفضل من نوع الدمج والإدراج. نوع الإدراج هو O (n^2) ولكن مع قوائم صغيرة من الأرقام ، يكون أسرع من دمج نوع!

حتى تتمكن من استخدام هذا كخوارزمية فرز عام كما هو مذكور هنا