《算法 第四版》算法6--归并排序

归并排序

-自然语言描述：

指的是将两个已经排序的序列合并成一个序列的操作。

归并过程为：比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。

-原地归并的抽象方法：

public static void merge(Comparable[] a, int start, int mid, int end){
  //将a[start..mid]和a[mid +1...end]归并
  int i = star,  j= mid + 1;
  for(int k = start; k<=end; k++)  //将a[start...end]复制到aux[start...end]
      aux[k] = a[k];

  for (int k = start; k<=end; k++)
    if (i > mid)                           a[k] = aux[j++];
    else if (j > end)                   a[k] = aux[i++];
    else if (less(aux[j], aux[i]))  a[k] = aux[j++];
    else                                     a[k] = aux[i++];
}

轨迹图

-自顶向下的归并排序：

public class Merge {

  private static Comparable[] aux;             // 归并所需的辅助数组

  public static void sort(Comparable[] a){        // 一次性分配空间
    aux = new Comparable[a.length];
    sort(a, 0, a.length - 1);
  }

  private static void sort(Comparable[] a, int start, int end){
    if (end <= start) return;
    int mid = start + (end - start)/2;            
    sort(a, start, mid);                                //将左半边排序
    sort(a, mid+1, end);                             //将右半边排序
    merge(a, start, mid, end);                    //原地归并的抽象方法
  }
}

自顶向下的归并排序的轨迹

调用轨迹

这两张图我也是想了好久才看懂一些，建议可以在纸上用二叉树画出来，会清晰很多。

-自底向上的归并排序

public class MergeBU {
  private static Comparable[] aux;                  //归并辅助函数
  
  public static void sort(Comparable[] a){
    int N = a.length;
    aux = new Comparable[N];
    for (int sz = 1; sz < N; sz = sz + sz)
        for (int lo = 0; lo < N - sz; lo += sz + sz)
            merge(a, lo, lo + sz - 1,Math.min(lo + sz + sz - 1,N - 1));
  }
}

自底向上的归并排序