ملخص
تتمثل طريقة فرز الدمج في دمج جدولين مرتبة (أو أكثر من اثنين) في جدول جديد مرتبة ، أي تقسيم التسلسل المراد فرزه إلى عدة متابعات ، يتم طلب كل بعد. ثم يتم دمج بعد المرتبة في التسلسل العام.
يتم تنفيذ فرز الدمج باستخدام العودية ، التي تنتمي إلى "تقسيم وقهر". يتم تقسيم المصفوفة المستهدفة إلى اثنين من الوسط ، ثم يتم فرز المصفمين بشكل منفصل. بعد الانتهاء من الفرز ، يتم "دمج" المصفوفتين معًا. أهم شيء في فرز الدمج هو عملية "الدمج". في عملية الدمج ، مطلوب مساحة إضافية تتوافق مع المصفمين اللذين يجب دمجهما.
صورة التكاثر:
خطوة
قم بتطبيق المساحة بحيث يكون حجمها هو مجموع تسلسلتين فرزتين. يتم استخدام هذه المساحة لتخزين التسلسل المدمج لوضع مؤشرين. الموضع الأولي هو موضع البداية للتسلسل المصنفين ، وقارن العناصر التي أشار إليها المؤشرين ، وتحديد عناصر صغيرة نسبيًا ووضعهما في المساحة المدمجة ، ونقل المؤشر إلى الموضع التالي. كرر الخطوة 3 حتى يصل المؤشر إلى نهاية التسلسل. انسخ جميع العناصر المتبقية من التسلسل الآخر مباشرة إلى نهاية التسلسل المدمج.
البيانات الخام:
3 5 2 6 2
الشرط المسبق للدمج هو فصل المصفوفات ، وتقسيمها إلى قسمين ، ثم يقسمها إلى قسمين ، ولا يمكن تقسيمها مرة أخرى ، ودمجها.
يتم فصل الجولة الأولى ، الفهرس 2 ((0+4)/2 = 2) هو الوسط
[3 5 2] [6 2]
الجولة الثانية من الانفصال ، منفصلة [3 5 2]
[3 5] [2] [6 2]
الجولة الثالثة من الانفصال ، منفصلة [3 5]
[3] [5] [2] [6 2]
دمج [3] [5]
[3 5] [2] [6 2]
دمج [3 5] [2]
[2 3 5] [6 2]
يتم فصل الجولة الرابعة ، تفصل [6 2]
[2 3 5] [6] [2]
دمج [6] [2]
[2 3 5] [2 6]
دمج [2 3 5] [2 6]
[2 2 3 5 6]
تنفيذ الكود (Java)
package com.coder4j.main.arithmetic.sorting ؛ دمج الطبقة العامة {private static int mark = 0 ؛ / ** * دمج الفرز * * param array * param low * param high * @return * / private static int [] sort (int [] int low ، int high) {int mid = (low + high) / 2 ؛ if (low <high) {mark ++ ؛ system.out.println ("thredth in progress" + mark + "الفصل اللاحق ، get") ؛ System.out.println ("[" + low + "-" + mid + "] [" + (mid + 1) + "-" + high + "]") ؛ // نوع الصفيف الأيسر (صفيف ، منخفض ، منتصف) ؛ // نوع الصفيف الأيمن (صفيف ، منتصف + 1 ، مرتفع) ؛ // الاندماج الأيسر واليمين (صفيف ، منخفض ، منتصف ، مرتفع) ؛ } صفيف الإرجاع ؛ } / ** * دمج المصفوفة * * param array * param low * param mid * param high * / private static void merge (int [] Array ، int low ، int mid ، int high) {system.out.println ("merge: [" + low + "-" + mid + "] و [" + 1) + 1) int [] temp = new int [عالية - منخفض + 1] ؛ int i = low ؛ // المؤشر الأيسر int j = mid + 1 ؛ // المؤشر الأيمن int k = 0 ؛ // انقل الرقم الأصغر إلى الصفيف الجديد أولاً بينما (i <= mid && j <= High) {if (Array [i] <array [j]) {temp [k ++] = array [i ++] ؛ } آخر {temp [k ++] = array [j ++] ؛ }} // قد تكون هناك عناصر متبقية في أحد المصفوفتين // حرك الرقم المتبقي على اليسار في الصفيف بينما (i <= mid) {temp [k ++] = صفيف [i ++] ؛ } // انقل الرقم المتبقي على اليمين إلى الصفيف بينما (j <= High) {temp [k ++] = array [j ++] ؛ } // اكتب الأرقام في صفيف الصفيف الجديد لـ (int m = 0 ؛ m <temp.length ؛ m ++) {array [m+low] = temp [m] ؛ }} / ** * دمج الفرز * * param array * @RETURN * / public static int [] sort (int [] array) {return sort (Array ، 0 ، Array.Length - 1) ؛ } main static void main (string [] args) {int [] array = {3 ، 5 ، 2 ، 6 ، 2} ؛ int [] sorted = sort (Array) ؛ System.out.println ("النتيجة النهائية") ؛ لـ (int i: sorted) {system.out.print (i + "") ؛ }}}نتائج اختبار الإخراج:
يتم تنفيذ الفصل الأول ، ويتم تنفيذ [0-2] [3-4] ، ويتم تنفيذ الفصل الثاني ، ويتم تنفيذ [0-1] [2-2] ، ويتم تنفيذ الفصل الثالث ، ويجري [2-2] أداء [1-1]: [0-0] و [1-1] [3-3] [4-4] دمج: [3-3] و [4-4] دمج: [0-2] و [3-4] النتيجة النهائية 2 2 3 5 6
بعد الاختبار ، يتوافق مع النتائج في المثال.