إدراج مباشر
من السهل فهم فكرة إدخال الفرز مباشرة ، ويبدو أن هذا:
1. قسّم الصفيف ليتم فرزه إلى جزأين: فرزها ولم يتم فرزها. في البداية ، يعتبر العنصر الأول يتم فرزه.
2. ابدأ بالعنصر الثاني ، ابحث عن الموضع المناسب للعنصر في المسجل الفرعي المصنف وأدخله.
3. كرر العملية أعلاه حتى يتم إدراج العنصر الأخير في المسجل الفرعي المطلوب.
4. يتم الانتهاء من الفرز.
مثال:
الفكرة بسيطة ، لكن الكود ليس من السهل الكتابة مثل فرز الفقاعات. بادئ ذي بدء ، كيف تحدد الموقف الصحيح؟ أكبر من أو يساوي اليسار ، أقل من أو يساوي اليمين؟ لا ، يجب النظر في العديد من الشروط الحدودية ، وهناك الكثير من الأحكام. ثانياً ، سيتطلب إدخال العناصر في صفيف حتماً نقل عدد كبير من العناصر. كيف تتحكم في حركتهم؟
في الواقع ، هذه ليست مشكلة في الخوارزمية نفسها ، ولها علاقة بلغة البرمجة. في بعض الأحيان ، تكون الخوارزمية نفسها ناضجة بالفعل ، ولا يزال يتعين تغييرها قليلاً عندما يتعلق الأمر بلغة البرمجة المحددة. ما نتحدث عنه هنا هو خوارزمية Java ، لذلك دعونا نتحدث عن Java.
لحل المشكلة المذكورة أعلاه ، قمنا بعمل القليل من التحسين للخطوة الثانية. لا نبدأ المقارنة من موضع البداية للدخول الفرعي ، ولكننا نبدأ مقارنة عكسية من ذيل المباراة الفرعية. طالما أنه أكبر من العدد الذي يحتاج إلى إدراجه ، فإننا نتحرك للخلف. حتى لا يكون الرقم أكبر من الرقم ، سيتم وضع الرقم المراد إدراجه في هذا الموضع الفارغ. لذلك ، يمكننا كتابة الكود التالي:
insertarray.java
الطبقة العامة insertarray {// array private [] arr ؛ // حجم البيانات الصحيحة في صفيف elems الخاص ؛ // Constructor Public InsertArray () {arr = new Long [50] ؛ } insertarray (int max) {arr = new long [max] ؛ } // إدراج بيانات الفراغ العام (القيمة الطويلة) {arr [elems] = value ؛ elems ++ ؛ } // إظهار Data public void display () {for (int i = 0 ؛ i <elems ؛ i ++) {system.out.print (arr [i]+"") ؛ } system.out.println () ؛ } // insert sort public void ersertsort () {long select = 0l ؛ لـ (int i = 1 ؛ i <elems ؛ i ++) {select = arr [i] ؛ int j = 0 ؛ لـ (j = i ؛ j> 0 && arr [j - 1]> = select ؛ j--) {arr [j] = arr [j - 1] ؛ } arr [j] = select ؛ }}} فئة الاختبار:
testinsertarray.java
الفئة العامة testInserTarray {public static void main (string [] args) {insertarray iarr = new insertarray () ؛ iarr.insert (85) ؛ iarr.insert (7856) ؛ iarr.insert (12) ؛ iarr.insert (8) ؛ iarr.insert (5) ؛ iarr.insert (56) ؛ iarr.display () ؛ iarr.insertsort () ؛ iarr.display () ؛ }} نتيجة الطباعة:
أداء الخوارزمية/التعقيد
الآن دعنا نناقش التعقيد الزمني لخوارزمية الإدراج المباشر. بغض النظر عن المدخلات ، فإن الخوارزمية تؤدي دائمًا جولات N-1 للفرز. ومع ذلك ، نظرًا لأن نقطة الإدراج لكل عنصر غير مؤكد وتتأثر بشكل كبير ببيانات الإدخال ، فإن تعقيدها غير مؤكد. يمكننا مناقشة أفضل المواقف والأسوأ والمتوسط.
1. والسبب هو أنه في هذه الحالة ، يجب مقارنة كل عنصر فقط مرة واحدة ولا يلزم نقله. التعقيد الزمني للخوارزمية هو o (n) ؛
2. أسوأ حالة: من الواضح أنه عندما يكون الصفيف الذي سيتم ترتيبه في ترتيب عكسي ، فهذا هو أسوأ حالة. في هذه الحالة ، يكون عدد المقارنات الخاصة بنا لكل جولة هو I-1 وعدد المهام هو i. إجمالي عدد المرات هو مجموع شروط N الأولى من السلسلة 2N-1 ، أي ، n^2. التعقيد الزمني للخوارزمية هو O (n^2) ؛
3. الوضع المتوسط: من التحليل أعلاه ، يمكننا الحصول على أن عدد عمليات الخوارزمية تحت الوضع المتوسط تقريبًا (n^2)/2 (ملاحظة: يعتمد الحساب هنا على المهمة والمقارنة. إذا كان يعتمد على الحركة والمقارنة ، فهو تقريبًا n^2/4). من الواضح أن تعقيد الوقت لا يزال O (n^2).
أما بالنسبة للتعقيد المكاني للخوارزمية ، فسيتم تنفيذ جميع الحركات داخل البيانات. النفقات العامة الوحيدة هي أننا قدمنا متغيرًا مؤقتًا (تسمى بعض هياكل البيانات "الحراس" في الكتب) ، وبالتالي فإن تعقيدها المكاني (مساحة إضافية) هو O (1).
خوارزمية الاستقرار
نظرًا لأنك تحتاج فقط إلى العثور على موضع ليس أكبر من الرقم الحالي ولا تحتاج إلى مبادلة ، فإن إدخال النوع مباشرة هو طريقة فرز مستقرة.
المتغيرات الخوارزمية
إذا كان هناك الكثير من البيانات التي يجب ترتيبها ، فسيؤدي ذلك إلى الكثير من النفقات العامة في كل مرة تنظر فيها من الخلف إلى الأمام. من أجل تحسين سرعة البحث ، يمكن استخدام البحث الثنائي لتحسين الأداء. نظرًا لأن كفاءة البحث الثنائي مرتفع للغاية ، يتم ضمان تعقيد O (n) ، ويمكن تحسين كفاءة البحث بشكل كبير عندما يكون هناك المزيد من البيانات أو تميل بيانات الإدخال إلى الأسوأ. في بعض الكتب ، تسمى هذه الطريقة للطي ونصف الفرز. تطبيق الكود معقد للغاية ويمكن نشره إذا كان لديك وقت في المستقبل.
بالإضافة إلى ذلك ، هناك أنواع إدراج ثنائية الاتجاه وأنواع إدراج الجدول. يتم تحسين نوع الإدراج ثنائي الاتجاه على أساس النوع القابل للطي ونصف الإدراج ، ويتم تقليل عدد الحركات إلى حد كبير ، حوالي n^2/8. ومع ذلك ، فإنه لا يتجنب عدد الحركات ولا يقلل من مستوى التعقيد. يغير نوع إدخال الجدول تمامًا هيكل التخزين ولا ينقل السجلات ، ولكن يجب الحفاظ على قائمة مرتبطة ، ويتم تعديل مؤشر القائمة المرتبطة بدلاً من نقل السجلات. لذلك ، لا يزال تعقيدها o (n^2).
لفرز الإدراج ثنائي الاتجاه وفرز إدخال الجدول ، يمكنك الرجوع إلى كتاب "بنية البيانات" التي تم تحريرها بواسطة Yan Weimin و Wu Weimin.
خوارزمية سيناريوهات قابلة للتطبيق
لا ينطبق فرز الإدراج عندما يكون الصفيف كبيرًا بسبب تعقيد O (n^2). ومع ذلك ، عندما يكون هناك القليل من البيانات نسبيًا ، فهو خيار جيد ، ويستخدم عمومًا كتوسيع للفرز السريع. على سبيل المثال ، في خوارزمية الفرز لـ STL وخوارزمية QSORT من stdlib ، يتم استخدام الفرز الإدراج كملحق للفرز السريع ويستخدم لفرز عدد صغير من العناصر. على سبيل المثال ، في تنفيذ طريقة الفرز المستخدمة في JDK 7 java.util.arrays ، عندما يكون طول الصفيف المراد فرزه أقل من 47 ، سيتم استخدام فرز الإدراج.