النوع الوظيفي الفعال
سؤال
أنا أقوم ببرمجة وظيفة لـ ti-nspire, ، لذلك لا يمكنني استخدام المدمج من داخل وظيفة. ما هي الخوارزمية الأكثر فعالية بشكل عام لفرز قائمة بالأرقام دون تعديل القائمة نفسها؟ (عودية وتقسيم القائمة هي لعبة عادلة ، وكذلك الاستخدام العام للرياضيات.)
المحلول
Mergesort واضحة وبسيطة وفعالة ومستقرة: تقسيم القائمة ، فرز متكرر ، ودمج النتائج.
لكي تكون أكثر تحديداً ، يأخذ Mergesort O (n log n) ، وهو الأمثل بشكل غير متمرس. أيضًا ، في الممارسة العملية (مع تعديل كل من الخوارزميات لفرز القالات الفرعية القصيرة باستخدام نوع من الأغراض الخاصة) ، يمكن أن يكون Mergesort منافسًا وثيقًا للرسائل السريعة المعدلة المستخدمة في المكتبات القياسية C/C ++.
تحرير: على عكس الأنواع الموجودة في مكانها مثل Quicksort و Sorted Tort ، يتطلب Mergesort ذاكرة مساعدة ، وهو أبسط للتنفيذ عن طريق النسخ بدلاً من التبديل.