前言
将一个大的无序数组有序,我们可以把大的数组分成两个,然后对这两个数组分别进行排序,之后在把这两个数组合并成一个有序的数组。由于两个小的数组都是有序的,所以在合并的时候是很快的。
一、递归的方式
通过递归的方式将大的数组一直分割,直到数组的大小为 1,此时只有一个元素,那么该数组就是有序的了,之后再把两个数组大小为1的合并成一个大小为2的,再把两个大小为2的合并成4的 …… 直到全部小的数组合并起来。
为方便理解我还准备了动图:
二、代码
public class MergeSort {
// 归并排序
public static int[] mergeSort(int[] arr, int left, int right) {
// 如果 left == right,表示数组只有一个元素,则不用递归排序
if (left < right) {
// 把大的数组分隔成两个数组
int mid = (left + right) / 2;
// 对左半部分进行排序
arr = mergeSort(arr, left, mid);
// 对右半部分进行排序
arr = mergeSort(arr, mid + 1, right);
//进行合并
merge(arr, left, mid, right);
}
return arr;
}
// 合并函数,把两个有序的数组合并起来
// arr[left..mif]表示一个数组,arr[mid+1 .. right]表示一个数组
private static void merge(int[] arr, int left, int mid, int right) {
//先用一个临时数组把他们合并汇总起来
int[] a = new int[right - left + 1];
int i = left;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= right) {
if (arr[i] < arr[j]) {
a[k++] = arr[i++];
} else {
a[k++] = arr[j++];
}
}
while(i <= mid) a[k++] = arr[i++];
while(j <= right) a[k++] = arr[j++];
// 把临时数组复制到原数组
for (i = 0; i < k; i++) {
arr[left++] = a[i];
}
}
}
然而面试官要你写个非递归式的归并排序怎么办?别怕,我这还撸了个非递归式的归并排序,代码如下:文章来源:https://www.toymoban.com/news/detail-639379.html
public class MergeSort {
// 非递归式的归并排序
public static int[] mergeSort(int[] arr) {
int n = arr.length;
// 子数组的大小分别为1,2,4,8...
// 刚开始合并的数组大小是1,接着是2,接着4....
for (int i = 1; i < n; i += i) {
//进行数组进行划分
int left = 0;
int mid = left + i - 1;
int right = mid + i;
//进行合并,对数组大小为 i 的数组进行两两合并
while (right < n) {
// 合并函数和递归式的合并函数一样
merge(arr, left, mid, right);
left = right + 1;
mid = left + i - 1;
right = mid + i;
}
// 还有一些被遗漏的数组没合并,千万别忘了
// 因为不可能每个字数组的大小都刚好为 i
if (left < n && mid < n) {
merge(arr, left, mid, n - 1);
}
}
return arr;
}
}
总结
性质:
1、时间复杂度:O(nlogn)
2、空间复杂度:O(n)
3、稳定排序
4、非原地排序文章来源地址https://www.toymoban.com/news/detail-639379.html
到了这里,关于0基础学C#笔记10:归并排序法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!