归并排序

算法2.4自顶向下的归并排序(升序)

  1. import edu.princeton.cs.algs4.In;
  2. import edu.princeton.cs.algs4.StdOut;
  4. public class Merge {
  5.     private static  Comparable[] aux;
  7.     private static boolean less(Comparable v, Comparable w){
  8.         return v.compareTo(w) < 0;
  9.     }//比较v是否小于w
  11.     private static void sort(Comparable[] a){
  12.         aux = new Comparable[a.length];
  13.         sort(a, 0, a.length-1);
  15.     }
  16.     private static void merge(Comparable[] a, int lo, int mid, int hi){
  17.         int i = lo;
  18.         int j = mid + 1;
  20.         for(int k = lo; k <= hi; k++){
  21.             aux[k] = a[k];
  22.         }
  24.         for(int k = lo; k <=hi; k++){
  25.             if(i > mid) a[k] = aux[j++];
  26.             else if(j > hi) a[k] = aux[i++];
  27.             else if(less(aux[j],aux[i])) a[k] = aux[j++];
  28.             else a[k] = aux[i++];
  29.         }
  30.     }
  32.     private static void sort(Comparable[] a, int lo, int hi){
  33.         if(hi <= lo) return;
  34.         int mid = (lo + hi)/2;
  35.         sort(a, lo, mid);
  36.         sort(a, mid+1, hi);
  37.         merge(a, lo, mid, hi);
  38.     }
  40.     private static void show(Comparable[] a){
  41.         for(int i = 0; i < a.length; i++)
  42.             StdOut.print(a[i] + " ");
  43.         StdOut.println();
  44.     }
  46.     public static void main(String[] args){
  47.         String[] a = In.readStrings();
  48.         sort(a);
  49.         show(a);
  50.     }
  52. }

要点

  1. 原地归并的抽象方法:
  1. private static void merge(Comparable[] a, int lo, int mid, int hi){
  2.         int i = lo;//左半部分索引
  3.         int j = mid + 1;//右半部分索引
  5.         for(int k = lo; k <= hi; k++){
  6.             aux[k] = a[k];//辅助数组aux
  7.         }
  9.         for(int k = lo; k <=hi; k++){//归并左右部分
  10.             if(i > mid) a[k] = aux[j++];//左半部分用完
  11.             else if(j > hi) a[k] = aux[i++];//右半部分用完
  12.             else if(less(aux[j],aux[i])) a[k] = aux[j++];//按大小插入
  13.             else a[k] = aux[i++];
  14.         }
  15.     }
  1. 对于长度为N的任意数组,自顶向下的归并排序需要1/2NlgN至NlgN次的比较
    证明:令C(N)表示长度为N的数组排序所需的比较次数,通过递归的sort()可以得到C(N)≤C([N/2]+C([N/2])+N,第一项第二项分别为左右部分排序时比较次数,第三部分即归并比较次数(less调用次数),可知第三部分在[N/2]和N之间变化,当右半部分元素全部小于左边,执行N/2次j++后比较结束,当两边大小交错,最多比较N次结束.当N == 2时,一二部分都为2,则C(2)=2C(2)+2,经过化简代换,C(N)=C(2)=n2**=NlgN**
  2. 对于长度为N的任意数组,自顶而下归并排序最多需要访问数组6NlgN次
    证明:每次归并,2N次复制(aux[i]=a[i]),2N次移回排好序元素(a[i]=aux[i]),加上最多比较时访问数组2N次(less(aux[j],aux[i]))
  3. compareTo的特殊性,导致只能按照字符串排序,因此数字排序有漏洞,如3 < 12;

自底向上的归并排序

  1. public static void sort(Comparable[] a){
  2.         int N = a.length;
  3.         aux = new Comparable[N];
  4.         for(int sz = 1; sz < N; sz = sz*2){
  5.             for(int lo = 0; lo < N-sz; lo += 2*sz){
  6.                 merge(a,lo,lo+sz-1, Math.min(lo+2*sz-1, N-1));
  7.             }//sz为子数组大小,lo为子数组索引,min()方法防止越界
  8.         }
  9.     }//一一归并,二二归并,四四归并,八八归并...

要点

  1. 算法2.4的2,3条同样适用

排序算法的复杂度

没有任何基于比较的算法能够保证长度为N的数组使用少于lg(N!)~NlgN次比较将长度为N的数组排序

证明:假设没有重复的主键,使用二叉树表示所有比较,树中的结点是一片叶子[i0,i1,i2…],表示排序完成且输入顺序就是0,1,2…,要么是一个内部结点[i:j]表示a[i]和a[j]之间进行了一次比较操作,左子树为a[i]a[j]后的操作.首先一棵树至少有N!个叶子节点,因为N个不同的逐渐一定有N!种排列;又由高度为h的树最多只可能有2个叶节点,因此N!≤叶子节点数量≤2,h即为最坏情况的比较次数,两侧取对数可得h至少为lgN!,而lgN!~NlgN

归并排序是一种渐进最优的基于比较的排序算法

已知算法2.4最坏情况下比较次数NlgN和任意基于比较的排序算法的最少比较次数增长级相同

归并排序的局限性

  1. 归并排序的空间复杂度不是最优的
  2. 实践中不一定会遇到最坏情况
  3. 除了比较,算法的其他操作(如访问数组)也可能很重要
  4. 不进行比较也可以进行某些数据排序

答疑

  1. 归并和希尔排序比较:

实际应用中,归并排序较快,但允许时间之间的差距在常数级别之内;

  1. 为什么不把aux[]声明为merge()的局部变量:
    为了避免每次归并时,即使归并很小的数组也要创建一个新的数组,这样创建新数组会成为运行时间的主要部分,更好的方案是将aux[]变为sort的局部变量,作为参数传递给merge();

  2. 数组中存在重复元素时归并排序表现如何:
    当所有元素都相同,加上一个判断a[mid]<=a[mid+1]就可以任务数组已经有序跳过merge(),从而使得任意有序的数组算法运行时间变为线性的;但当有多个不同重复值时,比如奇数为为a,偶数位为b,运行时间又回归线性对数(刚好满足所有的循环条件)

Review

  1. 自顶向下归并sort(src, 0, src.length-1 )即hi = src.lenght-1
  2. 自底向上归并N=src.length, 外层循环sz取值[1,N),内层lo取值[0,N-sz], min = lo, mid = lo + sz-1, hi = min(lo + 2*sz -1, N-1)
  3. 内循环lo每次改变2*sz