如何使用C#执行合并排序？

合并排序是一种使用分而治之方法的排序算法。它将数组分为两部分，然后针对这两部分中的每一个进行调用。继续此过程，直到对数组进行排序为止。

给出了一个演示C#中的合并排序的程序，如下所示-

示例

using System;
namespace QuickSortDemo {
   class Example {
      static public void merge(int[] arr, int p, int q, int r) {
         int i, j, k;
         int n1 = q - p + 1;
         int n2 = r - q;
         int[] L = new int[n1];
         int[] R = new int[n2];
         for (i = 0; i < n1; i++) {
            L[i] = arr[p + i];
         }
         for (j = 0; j < n2; j++) {
            R[j] = arr[q + 1 + j];
         }
         i = 0;
         j = 0;
         k = p;
         while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
               arr[k] = L[i];
               i++;
            } else {
               arr[k] = R[j];
               j++;
            }
            k++;
         }
         while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
         }
         while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
         }
      }
      static public void mergeSort(int[] arr, int p, int r) {
         if (p < r) {
            int q = (p + r) / 2;
            mergeSort(arr, p, q);
            mergeSort(arr, q + 1, r);
            merge(arr, p, q, r);
         }
      }
      static void Main(string[] args) {
         int[] arr = {76, 89, 23, 1, 55, 78, 99, 12, 65, 100};
         int n = 10, i;
         Console.WriteLine("Merge Sort");
         Console.Write("Initial array is: ");
         for (i = 0; i < n; i++) {
            Console.Write(arr[i] + " ");
         }
         mergeSort(arr, 0, n-1);
         Console.Write("\nSorted Array is: ");
         for (i = 0; i < n; i++) {
            Console.Write(arr[i] + " ");
         }
      }
   }
}

输出结果

上面程序的输出如下。

Merge Sort
Initial array is: 76 89 23 1 55 78 99 12 65 100
Sorted Array is: 1 12 23 55 65 76 78 89 99 100

现在让我们了解上面的程序。

在main()函数中，首先显示初始数组。然后，mergeSort()调用该函数以对数组执行合并排序。给出的代码片段如下。

int[] arr = {76, 89, 23, 1, 55, 78, 99, 12, 65, 100};
int n = 10, i;
Console.WriteLine("Merge Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
   Console.Write(arr[i] + " ");
}
mergeSort(arr, 0, n-1);

在函数中mergeSort()，q被计算为数组的中点。然后mergeSort()在创建的两个子数组上调用。最后，merge()称为合并这些子数组的。给出的代码片段如下。

if (p < r) {
   int q = (p + r) / 2;
   mergeSort(arr, p, q);
   mergeSort(arr, q + 1, r);
   merge(arr, p, q, r);
}

在该函数中merge()，提供了两个已排序的子数组。此函数基本上将这些子数组合并为单个数组，以便对结果数组也进行排序。给出的代码片段如下。

int i, j, k;
int n1 = q - p + 1;
int n2 = r - q;
int[] L = new int[n1];
int[] R = new int[n2];
for (i = 0; i < n1; i++) {
   L[i] = arr[p + i];
}
for (j = 0; j < n2; j++) {
   R[j] = arr[q + 1 + j];
}
i = 0;
j = 0;
k = p;
while (i < n1 && j < n2) {
   if (L[i] <= R[j]) {
      arr[k] = L[i];
      i++;
   } else {
      arr[k] = R[j];
      j++;
   }
   k++;
}
while (i < n1) {
   arr[k] = L[i];
   i++;
   k++;
}
while (j < n2) {
   arr[k] = R[j];
   j++;
   k++;
}
while (j < n2) {
   arr[k] = R[j];
   j++;
   k++;
}