上面给出了两个分别给出基于平均时间复杂度和最坏时间复杂度的两个例子，可以看到在第二层起，每个单元格中的元素时有序的，而单元格间的元素是无序的，需要在合并操作中将它们排好序放到一个合并的单元格中。

快速排序

实现简单，一般应用比其他排序算法都要快得多，另外一个诱人的特点是支持原地排序，只需一个很小的辅助栈，且将长度为 N 的数组排序的时间和 NlgN 成正比，其他的排序算法无法结合这两个特点。另外，快排的内循环比大多数排序算法都短小。其主要缺点是脆弱性，错误的实现会带来低劣的性能。^TOC

快排采用了分治的思想，先将数组分成两个子数组，对这两部分分别进行排序。快排与归并排序是互补的，归并排序将数组分成两个子数组分别进行排序，并将有序的子数组归并以将整个数组排序，而快排将数组排序的方式则是当两个子数组都有序时整个数组也就自然有序了。在归并排序中，一个数组被切分成两半，递归调用发生在处理整个数组之前；而在快排中，切分的位置取决于数组的内容，且递归调用发生在处理整个数组之后。

在上图中，将K作为分割点，第一次递归结束后，得到的结果如上所示，可见K最终被放到了一个合适的位置，它将不再移动，下面的排序则是在k左右的两块区域里递归进行，而这两块区域中的元素分别小于和大于K，因此易知当这两块区域的有序后，整个数组都有序了。分治实现代码如下所示：

/**
 * Rearranges the array in ascending order, using the natural order.
 * @param a the array to be sorted
 s*/
public static void sort(Comparable[] a) {
    StdRandom.shuffle(a);	// 打乱数据，消除对输入的依赖
    sort(a, 0, a.length - 1);
    assert isSorted(a);
}

// quicksort the subarray from a[lo] to a[hi]
private static void sort(Comparable[] a, int low, int high) {
    if (high <= low) return;
    int j = partition(a, low, high);
    sort(a, low, j-1);	// 将左半部分排序
    sort(a, j+1, high);		// 将右半部分排序
    assert isSorted(a, low, high);
}

快速排序递归地将子数组 a[low, high] 排序，先用 partition()方法将a[j]放到一个合适的位置，然后再用递归调用将其他位置的元素排序。如下图中，通过 partition()方法将数组的第一个元素作为pivot，即中轴点放到一个最终位置a[j]。该方法的关键在于切分，切分结束使得数组满足下面三个条件：

• 对于某个j，a[j] 已经排定
• a[low] 到 a[j-1] 中的所有元素都不大于 a[j]
• a[j] 到 a[high] 中所有元素都不小于 a[j]

因为每个切分过程总是能排定一个元素，用归纳法不难证明递归可正确地将数组排序：若左右子数组均有序，那么由左子数组、切分元素和右子数组组成的结果数组一定是有序的。

要完成切分方法，一般的做法是随意选取a[low]作为切分元素pivot，即那个会被排定的元素，pivot将数组分成左右两份，接着从左到右扫描数组的左端部分，直到找到一个大于等于pivot的元素a，再从右到左扫描数组的右端部分，直到找到一个小于等于pivot的元素b，交换a和b，过程如下图左边所示，如此重复，我们就可保证做指针i的左侧元素都不大于切分元素pivot，右指针j右侧的元素都不小于切分元素pivot，当这两个指针相遇时只需将切分元素a[low]和左子数组最右侧的元素a[j]交换然后返回j即可。

切分的具体逻辑如下面的代码块中的partition()所示，它按照a[low]的值v进行切分，当指针i和j相遇时主循环退出。在循环中，a[i]小于v时i不停右移，a[j]大于v时j不停左移，当其中一个指针停下时，通过交换a[i]和a[j]保证i左侧的元素都不小于v，j右侧的元素都不小于v，当两指针相遇时交换a[low]和a[j]，切分结束。

// partition the subarray a[low..high] so that a[low..j-1] <= a[j] <= a[j+1..high]
// and return the index j.
private static int partition(Comparable[] a, int low, int high) {
    int i = low, j = high + 1;
    Comparable v = a[low];
    while (true) {
        // find item on low to swap
        while (less(a[++i], v) && i < high);
        // find item on high to swap
        while (less(v, a[--j]) && j > low);
        // check if pointers cross
        if (i >= j) break;
        exchange(a, i, j);
    }
    // put partitioning item v at a[j]
    exchange(a, low, j);
    // now, a[low .. j-1] <= a[j] <= a[j+1 .. high]
    return j;
}

如上面右图所示，选取K作为切分点，指针i和j渐次左/右移，直到找到比切分点大/小的元素，交换这两个元素，继续移动，直至相遇，在上面的例子中一共经历了4次交换，其中最后一次交换发生在指针相遇时，将切分点K和左子数组最右侧元素a[j]交换。下面给出两个演示动图，以右图为例，首先选取最右侧的31为切分点pivot，左右指针右/左移，符合条件即换位，最后将切分点放到适当的位置，在这个例子中，十分巧合地，一次partition即将数组排序完成，而无需在子数组中递归分治。

堆排序

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于或大于它的父节点。前面已经写过一篇文章 二叉堆及堆排序的Java实现 ，在此对堆排序做个简单的回顾和总结。为了实现堆排序，常见的做法是^TOC

1. 用待排序的数组构造称最大堆
2. 将根结点和最后一个子结点的值互换，通过heapSize--将数组的最后一个元素从堆中删除，逐层检查，维护最大堆的性质
3. 重复上述步骤直到操作完根结点

当执行删除堆顶元素的操作时，常用的方式是将其与最末一个叶子结点进行交换，通过heapSize--将数组的最后一个元素从堆中删除，而此时的堆状态可能会违反大顶堆的定义，即父结点的值小于子结点的值，故需要对堆中数据进行重大顶堆化(remaxheapify)操作，通过将小的父结点下降维护大顶堆的性质。下面给出这一过程的实现：

/**
 * Helper functions to restore the heap invariant.
 * @param pq 堆数据存储数组
 * @param k 需要下沉的父结点
 * @param n 堆中的元素个数，用于判断是否操作到叶子结点层
 */
private static void sink(Comparable[] pq, int k, int n) {
    while (2*k <= n) {
        int j = 2*k;
        // 父结点不为叶子结点，同时如果左结点小于右结点
        // 则将指针移向右结点，即将子结点中较大的那个上移
        if (j < n && less(pq, j, j+1)) j++;
        // 左子结点的值不大于父结点的值
        // 并发问题或其他情况导致异常，结束
        if (!less(pq, k, j)) break;
        // 换位
        exchange(pq, k, j);
        // 由于某个子结点移位，导致其对应的子树结构发生了变化
        // 所以需要对这棵子树也进行下沉操作
        k = j;
    }
}

sink()函数通过设置记录待下沉结点的指针来实现各层级的下沉，避免了使用递归的方式，其中的逻辑看注释即可。下面给出堆排序的实现，由于堆数组的索引范围为[1, n]及完全二叉树的性质，所以可以最后一个父结点开始进行下沉操作，可以想象到，当对根结点（k=1）进行下沉操作时，其左子结点（k=2）和右子结点（k=3）已经分别成堆，那么只需对根节点调用sink()函数即可构造出一个完整的堆，当然对根结点的下沉可能需要对其各层子树的结构重新进行调整。

/**
 * Rearranges the array in ascending order, using the natural order.
 * @param pq the array to be sorted
 */
public static void sort(Comparable[] pq) {
    int n = pq.length;
    // 堆数组索引从1开始，0号位置弃用
    // 通过数组内元素的交换实现结点的下沉
    // 从而实现大顶堆的构建
    for (int k = n/2; k >= 1; k--) {
        sink(pq, k, n);
    }
    // 将大顶堆的堆顶元素和最末的叶子结点交换，并恢复堆的性质
    while (n > 1) {
        // 将最末的叶子结点与堆顶元素交换
        // 通过n--操作将此时最末的叶子结点即最大结点的从堆中删除
        // 此结点排序完成
        exchange(pq, 1, n--);
        // 从对顶开始，将较小的元素向下沉
        sink(pq, 1, n);
    }
}

下面给出两个示例动图，以右图为例，对于数组[6, 5, 3, 1, 8, 7, 2, 4]，在进行构造堆操作完成后，数组变成[8, 6, 7, 4, 5, 3, 2, 1]，完后再进行循环的交换和下沉最后得到有序的序列。

排序算法的复杂度

通过证明可以得出这样一个重要的结论：没有任何基于比较的算法能保证使用少于 lg(N!) ~ NlgN 次比较将长度为 N 的数组排序。该结论表明其他排序算法复杂度的下限。^TOC

而对归并排序可以得到的一个结论是：对于长度为 N 的任意数组，自底向下的归并排序需要 ¹⁄₂ NlgN 到 NlgN次比较，最多访问数组 6NlgN 次，NlgN 是其他排序算法复杂度的上限。

结合上面的两个结论可以得到：归并排序是一种渐进最优的基于比较排序的算法。更准确地说，归并排序在最坏情况下的比较次数和任意基于比较的排序算法所需的最少比较次数都是 ~NlgN。

Happy Sorting

首先分享一个估计是密集恐惧症杀手做的看上去颇为牛*的动图

下面给出 Youtube 上挺 hot 的一个关于归并排序的舞蹈的视频（需要开梯才能加载），该舞蹈其实属于一个系列，除了归并排序，还有关于冒泡排序等排序算法的舞蹈（见参考链接）。由Kátai Zoltán 和 Tóth László.摄于 Sapientia University，很多美国学校的老师为了增强上课的趣味性都在课堂上播了这些视频，感觉挺有意思，have fun ^TOC

参考

• 《算法》（第四版，Robert Sedgewick、Kevin Wayne 著，人民邮电出版社）
• Wikipedia: Shell Sort、Merge Sort、Bubble Sort、Cocktail Shaker Sort
• Hungarian folk dance on Youtube: Shell Sort、Merge Sort、Bubble Sort
• visualgo、Sorting Algorithms Animations

相关文章

• 二叉堆及堆排序的Java实现