أدخل هذا النوع مباشرة
1 فكرة الفرز:
يتم إدراج سجل RI المراد فرزه في السجلات التي تم فرزها بالفعل R1 ، R2 ، ... ، R (N-1).
للحصول على تسلسل عشوائي ، بدءًا من العنصر الثاني ، إدخال العنصر في الموضع المقابل في العنصر قبله بدوره. العناصر قبل أن يتم فرزها.
من الدرجة الأولى: أدخل العنصر الثاني في القائمة المطلوبة بالترتيب السابق (في هذا الوقت هناك عنصر واحد فقط في العنصر السابق ، بالطبع يتم طلبه). بعد ذلك ، يتم طلب العنصرين الأولين من هذا التسلسل.
النوع الثاني: أدخل العنصر الثالث في القائمة المطلوبة للطول السابق 2 بحيث يتم طلب العنصرين الأولين.
وما إلى ذلك حتى يتم إدراج العنصر التاسع في القائمة المطلوبة للطول السابق (N-1).
2 تطبيق الخوارزمية:
// إدراج مباشرة الفرز void reative_insert_sort (int num [] ، int len) {int i ، j ، key ؛ لـ (j = 1 ؛ j <len ؛ j ++) {key = num [j] ؛ أنا = J-1 ؛ بينما (i> = 0 && num [i]> مفتاح) {num [i+1] = num [i] ؛ أنا--؛ } num [i+1] = المفتاح ؛ }}3 تحليل الأداء:
3.1 تعقيد الفضاء: كما ذكر أعلاه ، يتم استخدام مفتاح الوحدة الإضافية ، وتعقيد الفضاء هو O (1)
3.2 تعقيد الوقت:
3.2.1 أفضل حالة: يتم بالفعل طلب السجلات التي سيتم فرزها ، ثم فرزها في رحلة واحدة ، تتم مقارنة الكلمات الرئيسية مرة واحدة ، ويتم نقل السجلات مرتين. العملية برمتها
عدد المقارنات
عدد السجلات تحركات
تعقيد الوقت o (n)
3.2.2 أسوأ حالة: السجلات المراد فرزها هي بالفعل في ترتيب عكسي ، ثم أوقات مقارنة الكلمات الرئيسية هي I (من I-1 إلى 0) ، وتحركات السجل (I+2) مرات. العملية برمتها
عدد المقارنات
عدد السجلات تحركات
تعقيد الوقت o (n^2)
3.2.3 متوسط تعقيد الوقت: o (n^2)
3.3 الاستقرار: مستقر
قم بطي نصف إدراج
1 فكرة الفرز:
استنادًا إلى الفرز المباشر ، يتم إدراج السجلات المراد فرزها RI في السجلات المرتبة بالفعل R1 ، R2 ، ... ، R (N-1). نظرًا لأن السجلات R1 و R2 و ... و R (N-1) قد تم فرزها ، يمكن استخدام "Half-Finding" عند البحث عن موضع الإدراج.
2 تطبيق الخوارزمية:
// أضعاف نصف إدراج فرز void binary_insert_sort (int num [] ، int len) {int i ، j ، key ، low ، high ، mid ؛ لـ (i = 1 ؛ i <len ؛ i ++) {key = num [i] ؛ منخفض = 0 ؛ عالية = I-1 ؛ Mid = (Low+High)/2 ؛ // ابحث عن نقطة الإدراج ، تكون نقطة الإدراج النهائية منخفضة بينما (منخفضة <= عالية) {if (key <num [mid]) High = Mid-1 ؛ آخر منخفض = منتصف+1 ؛ Mid = (Low+High)/2 ؛ } // نقل السجل لـ (j = i ؛ j> low ؛ j-) {num [j] = num [j-1] ؛ } // insert record num [low] = key ؛ }}3 تحليل الأداء:
3.1 تعقيد الفضاء: كما ذكر أعلاه ، يتم استخدام مفتاح الوحدة الإضافية ، وتعقيد الفضاء هو O (1)
3.2 تعقيد الوقت: على الرغم من أن البحث نصف الدعامة يقلل من عدد السجلات والمقارنات ، إلا أنه لا يقلل من عدد الحركات ، وبالتالي فإن التعقيد الزمني هو نفس خوارزمية البحث المباشر.
3.2.1 أفضل حالة: تعقيد الوقت o (n)
3.2.2 أسوأ حالة: تعقيد الوقت o (n^2)
3.2.3 متوسط تعقيد الوقت: o (n^2)
3.3 الاستقرار: مستقر