[lwptoc]

排序升级

上一篇文章总结了一些基础的排序算法，但是那些算法并不能应用在实际的程序设计中。因为除了希尔排序，其他算法的时间复杂度均为 $ O(n^2) $，若输入的数据很复杂，则算法的时间消耗是不可接受的。
本篇将会总结一些实用的排序算法，其中一些已经被一些系统的 API 使用了（比如 JDK 中的 Arrays.sort() 使用的就是升级版的快速排序）。

归并排序

归并排序的主要思想是：将两个已经排序的序列合并成一个序列。

步骤

1. 把 $n$ 个记录看成 $n$ 个长度为 $1$ 的有序子表；
2. 进行两两归并使记录值有序，得到 $ \frac{n}{2} $ 个长度为 $2$ 的有序子表；
3. 重复第二步直到所有记录归并成一个长度为 $n$ 的有序表为止。

轨迹

可以看到这个算法先两两排序，再将它们 4 个一归并，再扩大范围归并。事实上两两排序也是在归并中完成的，算法的核心是归并，所以叫做归并排序。另外，排序的间隔序列也可以反过来形成递归调用，叫做“自顶向下的归并”，上述叫做“自底向上的归并”。

代码

import java.util.Arrays;

public class MergeSort {

    private static int[] aux;

    public static void main(String[] args) {
        int[] testArr = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}; // 测试用例
        mergeSort(testArr);
        System.out.println(Arrays.toString(testArr));
    }

    private static void mergeSort(int[] arr) {
        // 进行lgN次两两归并
        int N = arr.length;
        aux = new int[N];
        for (int sz = 1; sz < N; sz <<= 1) // sz子数组大小
            for (int lo = 0; lo < N - sz; lo += sz + sz) // lo:子数组索引
                merge(arr, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
    }

    private static void merge(int[] arr, int lo, int mid, int hi) { // 将a[lo..mid] 和 a[mid+1..hi] 归并
        int i = lo, j = mid + 1;
        // 将a[lo..hi]复制到aux[lo..hi]
        if (hi + 1 - lo >= 0) {
            System.arraycopy(arr, lo, aux, lo, hi + 1 - lo);
            for (int k = lo; k <= hi; k++) // 归并回到a[lo..hi]
                if (i > mid)                arr[k] = aux[j++];
                else if (j > hi)            arr[k] = aux[i++];
                else if (aux[j] < aux[i])   arr[k] = aux[j++];
                else                        arr[k] = aux[i++];
        }
    }
}

快速排序

快速排序也是采用分治的思想，它和归并排序不同的是它不需要归并排序的两个部分，而是逐步将要排序的元素放到合适的地方。

步骤

1. 随机地取出一个元素 K
2. 找出不大于 K 的元素放到 K 的左边，不小于 K 的元素放到 K 的右边
3. 将 K 左边的元素和 K 右边的元素递归进行 1 操作

由于需要大量比较 K 的大小，所以输入的 K 必须足够随机，而每一遍递归都需要取一个随机的 K，所以实现时干脆先把输入打乱，这样可以尽可能消除输入数据对所需时间的影响。

轨迹

（省略了无交换的比较）

对于此算法来说，核心的步骤就是如何切分，把 K 放到合适的位置。
我们可以取每个子数组的第一位作为 K，与其后面的每个元素比较，找出从前往后大于或等于 K 的元素与从后往前小于或等于 K 的元素交换，当然了，如果找不到这样的元素就马上停止比较。最后把 K 放在最后一次比较的元素的位置（原本 K 在开始处）。

代码

import java.util.Arrays;
import java.util.Random;

/**
 * 快速排序基础版
 */
public class QuickSort {

    private static final Random random = new Random();

    public static void main(String[] args) {
        int[] testArr = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}; // 测试用例
        quickSort(testArr);
        System.out.println(Arrays.toString(testArr));
    }

    private static void quickSort(int[] arr) {
        shuffle(arr); // 消除对输入的依赖
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int lo, int hi) {
        if (hi <= lo) return;
        int j = partition(arr, lo, hi); // 切分
        quickSort(arr, lo, j - 1); // 将左半部分a[lo .. j-1]排序
        quickSort(arr, j + 1, hi); // 将右半部分a[j+1 .. hi]排序
    }

    /**
     * 切分数组并找出切分的元素的索引
     *
     * @param arr 数组
     * @param lo  开始
     * @param hi  结束
     * @return 用于切分的元素的索引
     */
    private static int partition(int[] arr, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        int k = arr[i];
        while (true) {
            while (arr[++i] < k) if (i == hi) break;
            while (arr[--j] > k) /*if (j == lo) break*/ ;
            if (i >= j) break;
            swap(arr, i, j);
        }
        swap(arr, lo, j);
        return j;
    }

    /**
     * 交换数组中的元素
     *
     * @param arr 输入数组
     * @param i   交换源
     * @param j   交换目标
     */
    private static void swap(int[] arr, int i, int j) {
        int t = arr[j];
        arr[j] = arr[i];
        arr[i] = t;
    }

    /**
     * 打乱一个数组
     *
     * @param arr 输入数组
     */
    private static void shuffle(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int r = i + random.nextInt(n - i);     // between i and n-1
            int temp = arr[i];
            arr[i] = arr[r];
            arr[r] = temp;
        }
    }
}

TODO: 改进快速排序

堆排序

总结

复杂度和稳定性如下表