有哪些网站可以做推广,朝阳做网站的公司,wordpress如何上传源码,学做网站论坛怎么样文章目录 前言一、递归的方式二、代码总结 前言
将一个大的无序数组有序#xff0c;我们可以把大的数组分成两个#xff0c;然后对这两个数组分别进行排序#xff0c;之后在把这两个数组合并成一个有序的数组。由于两个小的数组都是有序的#xff0c;所以在合并的时候是很… 文章目录 前言一、递归的方式二、代码总结 前言
将一个大的无序数组有序我们可以把大的数组分成两个然后对这两个数组分别进行排序之后在把这两个数组合并成一个有序的数组。由于两个小的数组都是有序的所以在合并的时候是很快的。 一、递归的方式
通过递归的方式将大的数组一直分割直到数组的大小为 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[mid1 .. 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];}}
}然而面试官要你写个非递归式的归并排序怎么办别怕我这还撸了个非递归式的归并排序代码如下
public class MergeSort {// 非递归式的归并排序public static int[] mergeSort(int[] arr) {int n arr.length;// 子数组的大小分别为1248...// 刚开始合并的数组大小是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;}// 还有一些被遗漏的数组没合并千万别忘了// 因为不可能每个字数组的大小都刚好为 iif (left n mid n) {merge(arr, left, mid, n - 1);}}return arr;}
}总结
性质 1、时间复杂度O(nlogn) 2、空间复杂度O(n) 3、稳定排序 4、非原地排序
