归并排序:要将一个数组排序,可以先(递归的)将它分成两半分别排序,然后将结果归并起来得到一个有序数组,它最吸引人的地方是能够保证将任意长度为N的数组排序所需的时间复杂度和NlogN成正比.
原地归并排序
实现归并排序简单粗暴的办法是创建一个新数组,然后将两个有序输入数组的按照大小一个个从小到大放进这个数组中.但是对大数据进行排序时,需要进行多次归并,每次归并时都要创建一个新数组来存储排序结果,这样会带来问题.
所以我们希望有一种办法能够原地归并,这样就可以先对前半部分进行排序,再对后半部分进行排序,然后在数组中移动元素而不需要创建额外空间.
下面代码实现了这种算法,它将所有涉及的元素复制进一个辅助数组里面,再把归并结果放回原数组.
//原地归并排序 public static void merge(Comparable[] a, int lo, int mid, int hi){ int i = lo,j = mid + 1; Comparable[] aux = new Comparable[a.length]; //辅助数组 for(int k = lo; k <= hi; k++){ aux[k] = a[k]; } for(int k = lo; k<=hi; k++){ //右边用尽 if(j>hi) a[k] = aux[i++]; //左边用尽 else if(i>mid) a[k] = aux[j++]; //左边大于右边 else if(less(aux[j],aux[i])) a[k] = aux[j++]; //右边大于等于左边 else a[k] = aux[i++]; } }
该方法把所有元素赋值进aux[]中,然后归并回a[]中.在归并时进行四个条件判断:
左半边用尽(取右半边元素)
右半边用尽(取左半边元素)
右半边的当前元素小于左半边的当前元素(取右半边元素)
右半边的当前元素大于等于左半边的当前元素(取左半边元素)
自顶向下的归并排序
基于递归实现的另一种归并,这也是分治思想最典型的一个例子,这段递归代码是归纳证明算法能够正确地将数组排序的基础:如果它能够将两个子数组排序,它就能够通过归并两个子数组将整个数组排序.
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); }
要对子数组a[lo..hi]进行排序,先将它分为a[lo..mid]和a[mid+1..hi]两部分,分别通过递归调用将它们单独排序,最后将有序的子数组归并为最后排序结果.
归并排序所需的时间和NlgN成正比.
3个改进
1.对小规模的子数组使用插入排序
2.测试数组是否有序
3.不将元素复制进辅助数组
自底向上的归并排序
思路:先归并那些微型数组,然后再归并成对归并得到的子数组,如此这般,直到我们将整个数组归并到一起.
首先我们两两归并(把每个元素想象成一个大小为1的数组),然后进行四四归并(将两个大小为2的数组归并成一个大小为4的数组),然后八八归并,一直下去.
算法实现
//自底向上的归并排序 public static void sort(Comparable[] a){ //进行lgN两两归并 int N = a.length; // sz 子数组大小 /*因为一次归并排序都是使用2组数据进行排序,所以每次递增2组数据的偏移量*/ for(int sz = 1; sz < N; sz = sz*2){ // lo 数组索引 /* lo结束条件 是因为如果排序的索引位置连1组数据个数都不够了 那就没必要处理了,因为排序至少需要1组多的数据*/ for(int lo = 0; lo < N-sz; lo += sz*2){ s merge(a,lo,lo+sz-1,Math.min(lo+2*sz-1,N-1)); } } }
最后一个子数组的大小只有在数组的大小是sz的偶数倍的时候才会等于sz(否则就会比sz小).
自底向上的归并排序适合用链表组织的数据,这种方法只需要重新组织链表链接就能将链表原地排序(不需要创建任何新的链表节点).