来，咱们聊聊排序

排序在计算周期中占有很大的比重，其实现方法也是多种多样，如选择排序、插入排序、希尔排序、归并排序、快速排序、冒泡排序、桶排序、堆排序等，如果再加着各种排序的优化算法，不同排序互相组合的算法，可选择的排序算法真是数不胜数。本文主要介绍一些应用最广的排序算法，并简要说明了它们的优缺点。

选择排序

从左至右，每次找一个最小的，顺序与前面的位置交换。复杂度恒定为：O(n^2)，即使在有序的情况下也如此。

for (i = 0; i < n; ++i)
    min = i;
    for (j = i + 1; j < n; ++j)
        if (a[j] < a[min])
            min = j
    exchange(a, i, min)

插入排序

从左至右，每次向右关注一位，并与前面比较，找到合适位置插入，如整理牌一样。顺序完全相反，最坏为O(n^2)，已经排序好，最优为O(n)

for (i = 1; i < n; ++i)
    for (j = i - 1; (j >= 0) && (a[i] < a[j]); --j)
        exch(a, i, j)

插入排序对部分有序的数组排序很快，能迅速顺理部分无序状态，很适合小规模数组。

希尔排序

插入排序在对大规模乱序数组排序时会很慢，因为可能一个小元素要经过不断的向前一步步移动才能插入到正确位置。所以就有人想出来是不是可以拉大比较距离，先把相距较远的比较，然后剩下的无序相隔距离较近，用插入就很合适了。第一个版本的希尔排序是Donald Shell在1959年发布的。不过每次进行距离多大的比较没有固定的说法，目前一般为：H = 3 * H + 1，取小于原数组长度三分之一的最大值开始。

if (h < n/3) h = 3 * h + 1
while (h >= 1)
    for (i = 0; i < n - h; ++i)
        for (j = i + h; (j < n) && (a[j] < a[i]); j += h)
            exchange(a, i, j)
    h = h / 3

至今希尔排序的性能还无法彻底分析，因为无法证明哪种递增序列是最好的。希尔排序对中小规模排序很适用，并且实现简单，在递增序列为h = 3 * h + 1时的最坏情况复杂度为：O(n ^ (3/2))。

归并排序

首先思考如果一个数组前后部分已排序，则如何进行排序最好

fun merge (a, lo, mid, hi)
    i = lo, j = mid + 1
    copy(aux, a)
    for (k = 0; k < n; ++k)
        if (i > mid) a[k] = aux[j++]
        else if (j > hi) a[k] = aux[i++]
        else if (aux[i] < aux[j]) a[k] = aux[i++]
        else a[k] = aux[j++]

然后把数组不断二分，直到只有一个元素，那这一个元素的数组肯定是有序的，所以我们有以下递归算法

fun sort (a, lo, hi)
    if (lo >= hi) return
    mid = (hi - lo) / 2
    sort(a, lo, mid)
    sort(a, mid + 1, hi)
    merge(a, lo, mid, hi)

归并排序的最好最坏情况都为O(nlogn)，归并排序是理论上的时间最优排序，但因为需要申请辅助数组，所以空间复杂度并不最优。

注：在寻找最优排序是，我们假设一个n长度的数组，那么它的排列组合有n!中，这n!中可能可以把它当作一颗二叉树的叶子，而我们的排序就是要从树根一直找到某个叶子，从根到这个叶子的高度即为复杂度。所以一棵n!叶子的树，平均高度为logn! ~ nlogn。所以排序算法理论的最优时间为O(nlogn)，但考虑到其他一些因素可能影响到排序时的策略，所以针对不同数据情况，还有更好的排序方式。

快速排序

快速排序被称为20世纪最伟大的十个算法之一，本文最开始那张T恤衫上的算法即为快速排序。它不需要申请额外辅助数组，平均复杂度也为O(nlogn)，但它比较脆弱，实现不好就会产生很差的性能。快速排序也是一种分治排序，每次选用一个元素作为参考，然后把数组以此数为界分成一边大一边小的两部分，此时分界的位置即为该元素在排序后的数组中的位置。

fun sort(a, lo, hi)
    if (lo >= hi) return
    j = partition(a, lo, hi)
    sort(a, lo, j)
    sort(a, j + 1, hi)

现在就需要实现如何找到某个分界元素的位置。

fun partition(a, lo, hi)
    i = lo + 1, j = hi
    while (i <= j) 
        if (a[lo] >= a[i]) ++i
        else if (a[lo] < a[j]) --j
        else exchange(a, i, j)
    exchange(a, lo, j)
    return j

可以看出如果每次选择的分界元素恰好可以等分数组，那么就会时间最优，而如果，分界元素恰好是最小最大，那么复杂度也能达到O(n^2)，所以快速排序是个喜欢随机的排序。可以在快排之前先打乱一遍数组。

三向切分的快排

有些时候数组中会有大量元素重复，而使用普通的快速排序，显然不够优化，所以我们把取样数设置为3。这样每一次递归可以把重复元素集中起来，减少重复元素的交换。

fun sort(a, lo, hi)
    lt = lo, gt = hi, i = lt + 1
    v = a[lo]
    while (i <= gt)
        if (a[i] < v) exchange(a, i++, lt++)
        else if (a[i] > v) exchange(a, i, gt--)
        else i++
    sort (a, lo, lt - 1)
    sort (a, gt + 1, hi)

这种对重复元素的适应性使得三向切分的快速排序成为排序库函数的最佳选择。

找“top k”

根据快速排序的特性，我可以实现一个找到一个无序数组的‘top k’（第几大，或第几小的数）的方法。

fun find(a, k)
    lo = 0, hi = n - 1
    while(hi >= lo)
        j = partition(a, lo, hi)
        if (j < k) lo = j + 1
        else if (j > k) hi = j - 1
        else return a[k]
    return a[0]

堆排序

以上归并排序有需要额外辅助空间的缺点，而快速排序的最坏情况为O(n^2)，而非O(nlogn)。而堆排序同时解决了以上两个缺点，既无需额外储存空间，又可以把最坏情况控制在O(nlogn)上。

堆排序需要用到二叉堆，二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级储存（不使用数组第一个位置）。

堆有序指一个二叉树的每个节点都大于等于它的两个字节点。所以意味着堆顶元素最大。

首先我们需要实现构建堆的算法，如果一个堆中的某些节点小于它的字节点，我们就需要把该节点向下沉。

fun sink(a[], k)
    N = a.length
    while (2 * k <= N)
        j = 2 * k
        if (j < N && a[j] < a[j+1]) j++
        if (a[j] <= a[k]) break
        exchange (a, j, k)
        k = j

实现了下沉函数后，我们可以用此来构建堆，从而完成排序

fun sort(a[])
    //构建堆
    N = a.length
    for (k = N / 2; k > 0; k--)
        sink(k)
    while(N > 1)
        exchange(a, 1, N--)
        sink(a, 1)

但堆排序也存在以下三个缺点：1，内循环比快排长；2，因为每次使用数组元素跨度大，不方便使用缓存；3，不是稳定排序。所以导致现代系统用堆实现排序的比较少。

Java中的排序

Java中的排序分别对元数据和对象数据采用了两个不同算法，对元数据使用的是DualPivotQuicksort，一种三向切分的快速排序的优化方案，而对对象排序使用的是TimSort，一种归并排序的优化方案。之所以如此，因为Java要保证在对象数据排序时要稳定，相同key的数据顺序不能在排序后被改变，所以使用了归并排序。而元数据没有多个key的情况，所以采用了更快，空间复杂度更优的快速排序。