c#代码实现排序算法之归并排序
程序员文章站
2022-03-24 13:53:22
...
归并排序的平均时间复杂度为O(nlogn),最好时间复杂度为O(nlogn),最坏时间复杂度为O(nlogn),空间复杂度为O(n),是一种稳定的算法。
1.将待排序序列r(1),r(2),…,r(n)划分为两个长度相等的子序列r(1),…r(n/2)和r(n/2+1),…,r(n)。
2.求解子问题:分别对这两个子序列进行排序,得到两个有序子序列。
3.合并:将这两个有序子序列合并成一个有序序列。
归并排序采用分治法。
public static void merger(int[] list, int low, int mid, int high)
{
int[] L = new int[mid - low + 2];
int[] R = new int[high - mid + 1];
L[mid - low + 1] = int.MaxValue;
R[high - mid] = int.MaxValue;
for (int i = 0; i < mid - low + 1; i++)
{
L[i] = list[low + i];
}
for (int i = 0; i < high - mid; i++)
{
R[i] = list[mid + 1 + i];
}
int j = 0;
int k = 0;
for (int i = 0; i < high - low + 1; i++)
{
if (L[j] <= R[k])
{
list[low + i] = L[j];
j++;
}
else
{
list[low + i] = R[k];
k++;
}
}
}
public static void cutSortArray(int[] list, int low, int high)
{
if (low < high)
{
int mid = (low + high) / 2;
cutSortArray(list, low, mid);
cutSortArray(list, mid + 1, high);
merger(list, low, mid, high);
}
}