如何使用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++; }