排序----归并排序
归并排序的特点：
- （优点）：能够保证将任意长度为N的数组排序所需时间和NlogN成正比。
- （缺点）：所需额外空间与N成正比。
归并排序是算法设计中分治思想的典型应用。
原地归并方法：
public static void merge(Comparable[] a,int lo,int mid,int hi){
//原地归并方法
int i=lo,j=mid+1;
for(int k =lo;k<=hi;k++)//将a[]复制到aux[]
aux[k] = a[k];
for(int k =lo;k<=hi;k++)
if(i>mid) a[k] = aux[j++];//左半边用尽（取右半边元素）
else if(j>hi) a[k] = aux[i++];//右半边用尽（取左半边元素）
else if(less(aux[j],aux[i])) a[k] = aux[j++];//右边当前元素<左边当前元素（取右边元素）
else a[k] = aux[i++];//右边当前元素>左边当前元素（取左边元素）
}- 对于长度为N的任意数组，自顶向下和自底向上的归并排序需要1/2*NlgN至NlgN次比较。
- 对于长度为N的任意数组，自顶向下和自底向上的归并排序最多访问数组6*NlgN次。
- 没有任何基于比较的算法能够保证使用少于lg(N!)~NlgN次比较将长度为N的数组排序。
- 归并排序是一种渐进最优的基于比较排序的算法。
有了归并方法，自顶向下的归并排序很容易实现（分治思想）：
public class Merge {
private static Comparable[] aux; //归并方法需要的辅助数组
public static void sort(Comparable[] a){
aux = new Comparable[a.length];
sort(a,0,a.length-1);
}
public static void sort(Comparable[] a,int lo,int hi){
if(hi<=lo)return;
int mid = lo+(hi-lo)/2;
sort(a,lo,mid);//左半边排序
sort(a,mid+1,hi);//右半边排序
merge(a,lo,mid,hi);//归并
}
//less()、exch()、isSorted()、main()方法见“排序算法模板”
}可以通过一些改进大幅缩短归并排序的运行时间，例如：
- 对小规模子数组使用插入排序。
- 测试数组是否已经有序。
- 不将元素复制到辅助数组。
自底向上的归并排序：
public static void sort(Comparable[] a){
int N = a.length();
aux = new Comparable[N];
for(int sz = 1;sz<N;sz = sz+sz) //sz子数组的大小
for(int lo=0;lo<N-sz;lo+=sz+sz) //lo:子数组索引
merge(a,lo,lo+sz-1,Math.min(lo+sz+sz-1, N-1));
}自底向上的归并排序算法适合用链表组织的数据。
算法改动：
快速归并：按降序将a[]的后半部分复制到aux[]，然后将其归并回a[]，这样可以去掉循环中检测某半边是否用尽的代码。
次线性的额外空间：用大小M将数组分为N/M块，可以实现算法使需要的额外空间减少到max(M,N/M):
- 每个块用选择排序排序
- 块之间归并排序排序
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017.11.30，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读