归并排序
归并,指合并,合在一起。归并排序(Merge Sort)是建立在归并操作上的一种排序算法。其主要思想是分而治之。
若将两个有序集合并成一个有序表,称为2-路归并,与之对应的还有多路归并。
怎么分
- 对于排序最好的情况来讲,就是只有两个元素,这时候比较大小就很简单,但是还是需要比较
- 如果拆分为左右各一个,无需比较即是有序的。
怎么治
借助一个辅助空数组,把左右两边的数组按照大小比较,按顺序放入辅助数组中即可。
以下面两个有序数组为例:
代码实现
public static void mergeSort(int[] arr){ if (arr == null || arr.length<2){ return; } process(arr,0,arr.length-1); } //分治过程 private static void process(int[] arr, int L, int R) { if (L == R) { return; } int mid =L+((R-L)>>1); process(arr,L,mid); process(arr,mid+1,R); //递归 merge(arr,L,mid,R); } private static void merge(int[] arr, int L, int M, int R ) { //设置辅助空间 int[] help= new int[R-L+1]; int i=0; int p1=L; int p2=M+1; //判断两边值是否越界 while(p1<=M && p2<R){ //当左边的值<右边的值 将左边的值拷贝到help里去 //否则将右边的值拷贝到help里去 help[i++] =arr[p1] <=arr[p2] ? arr[p1++] : arr[p2++]; } //如果p1没有越界,那么将p1剩下的东西全部拷贝到help中去 while(p1 <= M){ help[i++] =arr[p1++]; } //如果p2没有越界,那么将p2剩下的东西全部拷贝到help中去 while(p2 <=R){ help[i++]=arr[p2++]; } for ( i = 0; i <help.length ; i++) { arr[L+i]=help[i]; } }
时间复杂度
归并排序方法就是把一组n个数的序列,折半分为两个序列,然后再将这两个序列再分,一直分下去,直到分为n个长度为1的序列。然后两两按大小归并。如此反复,直到最后形成包含n个数的一个数组。
归并排序总时间 = 分解时间 + 子序列排好序时间 + 合并时间
无论每个序列有多少数都是折中分解,所以分解时间是个常数,可以忽略不计,则:
归并排序总时间 = 子序列排好序时间 + 合并时间
假设处理的数据规模大小为 n,运行时间设为:T(n),则T(n) = n,当 n = 1时,T(1) = 1
由于在合并时,两个子序列已经排好序,所以在合并的时候只需要 if 判断即可,所以n个数比较,合并的时间复杂度为 n。
- 将 n 个数的序列,分为两个 n/2 的序列,则:T(n) = 2T(n/2) + n
- 将 n/2 个数的序列,分为四个 n/4 的序列,则:T(n) = 4T(n/4) + 2n
- 将 n/4 个数的序列,分为八个 n/8 的序列,则:T(n) = 8T(n/8) + 3n
- …
- 将 n/2k 个数的序列,分为2k个 n/2k 的序列,则:T(n) = 2kT(n/2k) + kn
当 T(n/2k) = T(1)时, 即n/2k = 1(此时也是把n分解到只有1个数据的时候),转换为以2为底n的对数:k = log2n,把k带入到T(n)中,得:T(n) = n + nlog2n。
使用大O表示法,去掉常数项 n,省略底数 2,则归并排序的时间复杂度为:O(nlogn)文章来源:https://www.toymoban.com/news/detail-478151.html
算法稳定性
从原理分析和代码可以看出,为在合并的时候,如果相等,选择前面的元素到辅助数组,所以归并排序是稳定文章来源地址https://www.toymoban.com/news/detail-478151.html
到了这里,关于排序算法-归并排序详细讲解(MergeSort)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!