复习八大基础排序算法。分类：
- 插入类(直接插入、希尔排序)
- 选择类（直接选择、堆排序）
- 交换类（冒泡排序、快速排序）4. 归并排序
- 还有外部排序（桶排序？）
复杂度分析
- 空间复杂度： 2N + O(logN) （原始数组＋辅助数组＋递归过程）
时间复杂度： Nlog(N)
Principle: T(N) = 2*T(N/2) + N （两个子问题＋ merge）
证明可以画递归树、或代数演算、或归纳法（最容易推导）
代码如下
递归地（TopDown）
public static void mergeSort(Comparable[] a) { aux = new Comparable[a.length]; sort(a, 0, a.length - 1, 0); } private static void sort(Comparable[] a, int lo, int hi, int dep) {for (int i = 0; i < dep; i++) StdOut.print(" ");StdOut.println(String.format("sort(a[], %d, %d)", lo, hi)); if (hi <= lo) return; int mid = (lo + hi) / 2; sort(a, lo, mid, dep+1); sort(a, mid + 1, hi, dep+1); merge(a, lo, mid, hi); } private static void merge(Comparable[] a, int lo, int mid, int hi) { assert isSorted(a, lo, mid); assert isSorted(a, mid+1, hi); // 复制a[]到aux[] for (int k = lo; k <= hi; k++) aux[k] = a[k]; // 归并 int i = lo, j = mid+1; 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[i], aux[j])) a[k] = aux[i++]; // a[i]比a[j]小 else a[k] = aux[j++]; // j 位置较小 } assert isSorted(a); } 图示
非递归地（BottomUp）
public static void bottomUpMergeSort(Comparable[] a) { aux = new Comparable[a.length]; int N = a.length; for (int sz = 1; sz < N; sz += sz) // sz是子序列的长度，依次为 1, 2, 4, 8, 16, ... ，直到 N for (int lo = 0; lo < N - sz + 1; lo += 2*sz) // lo是合并所得子序列的下标，如sz=2时，lo依次为 0, 4, 8,... merge(a, lo, lo+sz-1, Math.min(lo+2*sz-1, N-1)); }