كود التنفيذ وأفكار نوع الدمج

فكر أولاً في كيفية دمج تسلسلين مرتبين. هذا بسيط للغاية. فقط قارن الرقم الأول من التسلسلين وخذ الرقم الأصغر أولاً. بعد أخذه، احذف الرقم في التسلسل المقابل. ثم قارنها إذا كان أحد الأعمدة فارغًا، فما عليك سوى حذف بيانات العمود الآخر واحدًا تلو الآخر.

انسخ رمز الكود كما يلي:

عرض الرمز
// دمج المصفوفات المرتبة a[] و b[] في c[]
باطلة MemeryArray (int a []، int n، int b []، int m، int c [])
{
كثافة العمليات ط، ي، ك؛

ط = ي = ك = 0؛
بينما (i ​​< n && j < m)
{
إذا (أ[i] <ب[ي])
c[k++] = a[i++];
آخر
c[k++] = b[j++];
}

بينما (ط < ن)
c[k++] = a[i++];

بينما (ي <م)
c[k++] = b[j++];
}

يمكن ملاحظة أن كفاءة دمج التسلسل المرتب عالية نسبيًا ويمكن أن تصل إلى O(n).

بعد حل مشكلة دمج التسلسلات المرتبة المذكورة أعلاه، دعونا نلقي نظرة على نوع الدمج. الفكرة الأساسية هي تقسيم المصفوفة إلى مجموعتين A وB. إذا كانت جميع البيانات في هاتين المجموعتين مرتبة، فيمكن بسهولة هاتين المجموعتين. يتم فرز البيانات. كيف نحافظ على البيانات في هاتين المجموعتين بالترتيب؟

يمكن تقسيم المجموعتين A وB إلى مجموعتين. وقياسا على ذلك، عندما تحتوي المجموعة المنفصلة على بيانات واحدة فقط، يمكن اعتبار أن المجموعة قد وصلت إلى النظام، ومن ثم يمكن دمج المجموعتين المتجاورتين. بهذه الطريقة، يتم إكمال فرز الدمج عن طريق تحليل المصفوفة أولاً بشكل متكرر ثم دمج المصفوفة.

انسخ رمز الكود كما يلي:

عرض الرمز
// سيتم دمج تسلسلين مرتبين a[first...mid] وa[mid...last].
دمج باطلة (int a[]، int first، int mid، int last، int temp[])
{
إنت ط = الأول، ي = منتصف + 1؛
int m = mid, n = last;
كثافة العمليات ك = 0؛

بينما (i ​​<= m && j <= n)
{
إذا (أ[i] <= أ[ي])
temp[k++] = a[i++];
آخر
temp[k++] = a[j++];
}

بينما (ط <= م)
temp[k++] = a[i++];

بينما (ي <= ن)
temp[k++] = a[j++];

لـ (i = 0; i < k; i++)
a[first + i] = temp[i];
}
دمج باطلة (int a[]، int first، int last، int temp[])
{
إذا (الأول <الأخير)
{
int mid = (الأول + الأخير) / 2؛
mergesort(a, first, mid, temp); // تم فرز الجانب الأيسر
mergesort(a, mid + 1, last, temp); // تم فرز الجانب الأيمن
mergearray(a, first, mid, last, temp); // دمج المصفوفتين المرتبتين
}
}

منطقي MergeSort(int a[], int n)
{
int *p = new int[n];
إذا (ع == فارغة)
عودة كاذبة.
mergesort(a, 0, n - 1, p);
حذف[] ص;
عودة صحيحة؛
}

كفاءة فرز الدمج عالية نسبيًا. افترض أن طول التسلسل هو N. يتطلب الأمر خطوات logN لتقسيم التسلسل إلى تسلسلات عشرية. كل خطوة هي عملية دمج التسلسل المرتب ويمكن تسجيل التعقيد الزمني كـ O(. N)، لذا فإن الإجمالي هو O(N*logN). نظرًا لأن فرز الدمج يعمل على البيانات المجاورة في كل مرة، فإن العديد من طرق الفرز للفرز المدمج (الفرز السريع، الفرز المدمج، فرز التل، فرز الكومة) في O(N*logN) تكون أيضًا فعالة نسبيًا.