مقدمة
تعقيد Mergesort للمدخلات التي تم فرزها في الاتجاه المعاكس هو O (n^2) ، ويتم إنشاء Timsort عن طريق تحسين الاندماج لهذا الموقف. متوسط التعقيد هو n*o (log n) ، وأفضل حالة O (n) ، وأسوأ الحالات هي n*o (log n). و Timsort هو نوع الاستقرار. تتمثل الفكرة في تقسيم العمود المصنف أولاً ، ثم دمج الأقسام ، والتي تبدو كما هي خطوة دمجورت ، ولكن هناك بعض التحسينات للبيانات العكسية والواسعة النطاق.
فكرة التحسين لدمج الفرز
هناك العديد من طرق التحسين لدمج الفرز:
مثل الفرز السريع ، يمكنك استخدام Insert Forting أو تحديد الفرز للمصفوفات الصغيرة لتجنب المكالمات العودية.
قبل أن يتم استدعاء الدمج () ، يمكنك تحديد ما إذا كان [MID] أقل من أو يساوي [MID+1]. إذا كان الأمر كذلك ، فلن تكون هناك حاجة للاندماج ، يتم طلب الصفيف بالفعل. السبب بسيط للغاية. نظرًا لأن الطوائف الفرعية قد تم طلبها بالفعل ، فإن [Mid] هو الحد الأقصى لقيمة المسجل الفرعي الأول ، و [Mid+1] هو الحد الأدنى للقيمة الفرعية الثانية. عندما [منتصف] <= a [mid+1] ، يتم طلب الصفيف ككل.
لتوفير الوقت نسخ عناصر إلى الصفيف المساعد ، يمكن تبديل أدوار الصفيف الأصلي والمصفوفة الإضافية في كل مستوى من المكالمة العودية.
تحتاج عملية الدمج في طريقة الدمج () إلى تحديد ما إذا كان I و J قد عبروا الحدود ، أي أنه تم استخدام نصف الحافة. طريقة أخرى لإزالة الكود الذي يكتشف ما إذا كان قد تم استنفاد نصف الجانب. الخطوة المحددة هي نسخ النصف الثاني من المصفوفة A [] إلى aux [] بترتيب تنازلي ، ثم الاندماج من كلا الطرفين. بالنسبة للصفائف {1،2،3} و {2،3،5} ، يتم نسخ أول سفر فرعي كالمعتاد ، ويتم نسخ الثانية من الخلف إلى الأمام ، والعنصر النهائي في AUX [] هو {1،2،3،5،3،2}. عيب هذه الطريقة هو أنه يجعل فرز الدمج يصبح فرزًا غير مستقر. تطبيق الكود كما يلي:
دمج void (int [] a ، int lo ، int mid ، int hi ، int [] aux) {for (int k = lo ؛ k <= mid ؛ k ++) {aux [k] = a [k] ؛} for (int k = mid+1 ؛ k <= hi ؛ k ++) {aux [k] = a hi - k+mid+1] ؛ // من الطرفين إلى الوسط لـ (int k = lo ؛ k <= hi ؛ k ++) if (aux [i] <= aux [j]) a [k] = aux [i ++] ؛ آخر a [k] = aux [j--] ؛}خطوات تيمسبورت
تقسيم
تتمثل فكرة التقسيم في مسح الصفيف مرة واحدة ، واستخدام التسلسل الإيجابي المستمر (إذا تم فرزه ترتيب تصاعدي ، فإن التسلسل الإيجابي هو تسلسل تصاعدي) ، أو [لضمان استقرار خوارزمية الفرز) كقسم (تشغيل). إذا كان تسلسلًا عكسيًا ، فقم بعكس العناصر في القسم. على سبيل المثال
1 ، 2 ، 3 ، 6 ، 4 ، 5 ، 8 ، 6 ، 4 نتائج التقسيم
[1،2،3،6] ، [4،5،8] ، [6،4]
ثم عكس التسلسل العكسي
[1،2،3،6] ، [4،5،8] ، [4،6]
دمج
النظر في مثال متطرف ، على سبيل المثال ، أطوال الأقسام هي 10000 و 10 و 1000 و 10 و 10 و 10 ، بالطبع نأمل أن ندمج 10 10 إلى 20 و 20 و 1000 إلى 1020 أولاً. إذا اندمجنا من اليسار إلى اليمين ، فسنستخدم المصفوفة 10000 ومجموعة من الأرقام الصغيرة في كل مرة ، وهو مكلف للغاية. حتى نتمكن من استخدام استراتيجية لتحسين ترتيب الدمج.
مثال
أخذ ConperableTimsort.sort () في Java كمثال ، يتم استخدام مكدس التشغيل لتحديد ما إذا كان ينبغي دمجه.
if (nremaining <min_merge) {int initrunlen = countrunandmakeascending (a ، lo ، hi) ؛ BinarySort (a ، lo ، hi ، lo + initrunlen) ؛ يعود؛ }فرز أقل من min_merge (32) ، وفرز مباشرة مع الإدراج الثنائي بعد التقسيم
int minrun = minrunlength (nremaining) ؛ do {// اكتشف موضع البداية للقسم التالي ، وكذلك قلب التسلسل العكسي int Runlen = countrunandMakeAscending (a ، lo ، hi) ؛ // تأكد من أن عمليات التشغيل في مكدس التشغيل أكبر من Minrun. إذا كان القسم الحالي صغيرًا جدًا ، فقم بإخراج العناصر من الخلف لتعويض (Runlen <minrun) {int force = nremaining <= minrun؟ nremaining: minrun ؛ BinarySort (a ، lo ، lo + force ، lo + runlen) ؛ Runlen = قوة ؛ } // put rot in the Run stack ts.pushrun (lo ، runlen) ؛ // الحكم على ما إذا كان ينبغي دمجها. أبدأ من أعلى المكدس وأعلم أنه لا يمكن دمجه // 1. Runlen [i - 3]> Runlen [i - 2] + Runlen [i - 1] // 2. Runlen [i - 2]> runlen [i - 1] ts.mergeCollapse () ؛ lo += runlen ؛ nremaining -= runlen ؛ } بينما (nremaining! = 0) ؛ // دمج جميع عمليات التشغيل المتبقية لإكمال فرز التأكيد lo == hi ؛ // دمج التشغيل المتبقي ts.mergeForCeCollapse () ؛ تأكيد ts.stackSize == 1 ؛النظر في وظيفة أكثر أهمية
/ *** إذا تمت إضافة أطوال آخر 2 أشواط أطول من المباراة السابقة ، فاستخدم التشغيل في الوضع الأوسط والتشغيل بأطوال أمامية وخلفية أقصر لدمج*إذا تمت إضافة أطوال 2 أشواط أقصر من المركز السابق ، ثم دمج اثنين من التشغيل*/ private void mergecollapse () if (n> 0 && runlen [n-1] <= runlen [n] + runlen [n + 1]) {if (runlen [n-1] <runlen [n + 1]) n-- ؛ ميرجيت (ن) ؛ } آخر إذا (runlen [n] <= runlen [n + 1]) {mergeat (n) ؛ } آخر {break ؛ // تم تأسيس Instariant}}