三、快速排序

快速排序通常叫做“快排”，它应该是应用最广泛的一个排序算法了，很多编程语言内置的排序工具，都或多或少使用到了快速排序，因为快速排序的时间复杂度可以达到 O(nlogn)，并且是原地排序，前面介绍的几种排序算法都无法将这两个优点结合起来。

快排和归并排序类似，都采用了分治思想，但是它的解决思路却和归并排序不太一样。如果要排序一个数组，我们可以从数组中选择一个数据，做为分区点（pivot），然后将小于分区点的放到分区点的左侧，大于分区点的放到其右侧，然后对于分区点左右两边的数据，继续采用这种分区的方式，直到数组完全有序。

概念读起来可能有点抽象，这里我画了一张图来帮助你理解整个排序的过程：

上图展示了第一次分区的过程，假设要排序的数组的下标是 p ~ r，我们取数组的最后一个元素 5 做为分区点，然后比 5 小的数字 0 3 1 2 移动到 5 的左边，比 5 大的数字 9 6 8 7 移动到 5 的右边。

然后以数字 5 为分界点，其左边的数字（下标为 p ~ q - 1），以及右边的数字（下标为 q + 1 ~ r），分别再进行同样的分区操作，一直分下去，直到数组完全有序，如下图：

下面的动图展示了快速排序的完整过程（注意动图中是选择第一个元素做为分区点的）：

如果使用一个简单的公式来表示快速排序，可以写成这样：

int q = partition(data, p, r);

quick_sort(data, p, r) = quick_sort(data, p, q - 1) + quick_sort(data, q + 1, r);

这里有一个 partition 分区函数，它的作用是选择一个分区点，并且将小于分区点的数据放到其左边，大于分区点的放到其右边，然后返回分区点的下标。其实这个 partition 分区函数是快速排序实现的关键，那究竟怎么实现这个函数呢？很容易想到的一种方式是：直接遍历一次原数组，依次取出小于和大于分区点的数据，将其各自存放到临时数组中，然后再依次拷贝回原数组中，过程如下图：

相信你也看出来了，这样做虽然简单，但是存在一个缺陷，那就是每次分区都会使用额外的存储空间，这会导致快速排序的空间复杂度为 O(n)，那么就不是原地排序了。所以快速排序使用了另一种方式来实现分区，并且没有借助额外的存储空间，它是怎么实现的呢？我还是画了一张图来帮助你理解：

这个分区的过程可能不太好理解，你可以多看几遍上面的图，我们声明了两个指针 i 和 j，从数组的最开始处向后移动，这里的移动规则有两个：一是如果 j 所在元素大于分区点，那么 j 向后移动一位，i 不变；二是如果 j 所在元素小于分区点，那么交换 i 和 j 所在元素，然后 i 和 将 j 同时向后移动一位。

终止的条件是 j 移动至数组末尾，然后交换分区点和 i 所在的元素，i 就是分区点的下标。

理解了这个过程之后，再来看快速排序的代码实现，就会非常的简单了，下面是一个示例：

public class QuickSort extends AbstractSort {
    @Override
    public void sort(Object[] nums) {
        if (nums == null || nums.length <= 1){
            return;
        }
        sortHelper(nums, 0, nums.length - 1);
    }
    private void sortHelper(Object[] data, int p, int r){
        if (p >= r){
            return;
        }
        int q = partition(data, p, r);
        sortHelper(data, p, q - 1);
        sortHelper(data, q + 1, r);
    }
    private int partition(Object[] data, int p, int r){
        Object pivot = data[r];
        int i = p, j = p;
        while (j < r){
            if (compare(data[j], pivot)) {
                swap(data, i, j);
                i++;
            }
            j++;
        }
        swap(data, r, i);
        return i;
    }
}

3.1 算法分析

快速排序的时间复杂度的表示方法其实和归并排序类似，在最好的情况下，每次分区都能够均匀的将数组一分为二，那么时间复杂度可表示为 T(n) = 2 * T(n/2) + n，由上面的归并排序公式分析可以得出，最后的时间复杂度可以表示为 O(nlogn)，尽管每次分区并不总会是最好情况，但是平均情况下，其时间复杂度还是在 O(nlogn) 左右的。

仔细分析一下，其实快速排序的简洁快速主要体现在：每次分区的时候，数组中的元素其实都在和一个定值比较并判断是否交换，扫描一遍数组之后，便不会再有数据交换了，而归并排序则是在交换比较元素之后，会重新把数组拷贝回原数组，所以可以得出结论，在多数情况下，快速排序其实比归并排序更快，尽管它们的时间复杂度都可以表示为 O(nlogn)。

快速排序另一个重要的特性是原地排序，因为分区的过程中并没有使用到额外的存储空间，空间复杂度是 O(1)，但很遗憾的是，快速排序是不稳定的，因为在分区的过程当中，数据会跳着进行交换，你可以结合我上面的图理解一下。

3.2 算法优化

快速排序作为一种在编程语言中应用很多的算法，很多程序语言设计专家都对其进行了大量的优化，接下来我们可以了解几种比较常用的优化策略。

使用插入排序

在数据量较少的情况下，可以使用插入排序，很多编程语言内置的排序算法都使用到了这个优化办法。

分区点选择

在上面的讲解中，我直接是以数组最后一个元素做为快速排序的分区点，这样做虽然简单，但是可能存在效率低下的情况，例如要排序的数据本来就是或接近有序的，那么每次分区数据的分布都极不均匀，时间复杂度就会退化。

快速排序最理想的情况是，每次分区都能够均匀的将数据一分为二，为了达到或者接近这种情况，分区点的选择其实可以更讲究一点，常用的方法有：随机法，我们可以随机的选择数组中一个数字做为分区点；三数取中，每次都随机的从数组中取出三个数，然后取三个数中间的那一个做为分区点。

三向切分

如果数组中存在大量重复的元素，那么重复的元素其实并不用排序了，但是上面的分区方法还是会把重复的元素切分为更小的数组。针对这种情况，可以使用三向切分的办法，即把数据切分为三份，分别是小于分区点、等于分区点、大于分区点的元素，而等于分区点的元素则不用继续切分。

下面是三向切分的一个代码示例，你可以结合代码来理解一下：

public class QuickSort3Way extends AbstractSort{
    @Override
    public void sort(Object[] nums) {
        if (nums == null || nums.length <= 1){
            return;
        }
        sortHelper(nums, 0, nums.length - 1);
    }
    @SuppressWarnings({"unchecked", "rawtypes"})
    private void sortHelper(Object[] data, int p, int r){
        if (p >= r){
            return;
        }
        int lt = p, i = p + 1, gt = r;
        Comparable pivot = (Comparable) data[p];
        while (i <= gt){
            int cmp = pivot.compareTo(data[i]);
            if (cmp > 0){
                swap(data, lt++, i++);
            } else if (cmp < 0){
                swap(data, i, gt--);
            } else{
                i++;
            }
        }
        sortHelper(data, p, lt - 1);
        sortHelper(data, gt + 1, r);
    }
}

四、堆排序

要理解堆排序，必须得先明白什么是二叉堆。二叉堆（以下简称堆）是一种很优雅的数据结构，它是一种特殊的二叉树，满足二叉树的两个特性便可以叫做堆：

• 是一个完全二叉树
• 堆中任意一个节点的值都必须大于等于（或者小于等于）其子树中的所有节点值

对于节点大于等于子树中节点值的堆，叫做大顶堆，反之则叫做小顶堆，以下是几个堆的例子：

从定义和上图中可以看到，堆的一个特点便是，堆顶元素就是堆中最大（或最小）的元素。堆其实可以使用数组来存储，堆顶元素就是数组的第一个元素，并且对于任意下标为 i 的节点，其左子节点是 2 * i + 1，右子节点是 2 * i + 2，有了这个对应关系，堆在数组中的存储就是这样的：

理解了什么是堆之后，接下来进入正题，看看如何基于堆实现排序。堆排序的步骤一般有两个，分别是构造堆和排序，下面依次介绍。

4.1 构造堆

构造堆指的是将无序的数组构造成大顶堆，使其符合大顶堆的特征，举一个例子，对于一个完全无序的数组，其原始的排列顺序就像下图这样：

要使其变成大顶堆，我们可以这样做：从第一个非叶子节点（叶子节点指的是树中没有子节点的节点）开始，依次将其和子节点的值进行比较，根据大顶堆的特性，如果节点的值小于子节点的值，则将其和较大的子节点的值进行交换，然后再依次向下比较，直到叶子节点。

例如上图中的数据，第一个非叶子节点是 3，所以就从 3 开始进行比较，整个过程如下图：

4.2 排序

构造堆完成之后，接下来便是排序了，前面已经提到过，大顶堆有一个重要的特性是其堆顶元素是堆中的最大元素，因此我们可以每次取堆顶的元素，将其放到数组的末尾，然后将堆重新组织，继续取堆顶元素，这样将堆中的元素依次取出之后，整个数组便是有序的了，你可以参考下图理解整个过程：

你也可以结合代码来看一下，下面是一个示例：

public class HeapSort extends AbstractSort{
    @Override
    public void sort(Object[] nums) {
        if (nums == null || nums.length <= 1){
            return;
        }
        buildHeap(nums, nums.length);
        for (int i = nums.length - 1; i > 0; i--) {
            swap(nums, 0, i);
            heapify(nums, 0, i);
        }
    }
    private void buildHeap(Object[] data, int n){
        for (int i = (n - 1) / 2; i >= 0; i--) {
            heapify(data, i, n);
        }
    }
    private void heapify(Object[] data, int i, int n){
        while (true){
            int max = i;
            if (2 * i + 1 <= n - 1 && compare(data[max], data[2 * i + 1])) {
                max = 2 * i + 1;
            }
            if (2 * i + 2 <= n - 1 && compare(data[max], data[2 * i + 2])) {
                max = 2 * i + 2;
            }
            if (i == max) break;
            swap(data, max, i);
            i = max;
        }
    }
}

4.3 算法分析

堆排序的时间复杂度比较好分析，堆是一个完全二叉树，完全二叉树和满二叉树的高度都是 logn，每次重新构建堆的时间消耗是 logn，排序至少需要遍历数组每个元素，时间消耗是 n，因此堆排序的总体时间复杂度便是 O(nlogn)。排序的过程中没有使用到额外的存储空间，空间复杂度是 O(1)，是原地排序。

堆排序并不是稳定的，你可以结合上面的图理解一下，数据在交换的过程当中是像选择排序一样跳着交换的，因此相同数据的前后顺序可能发生变化。

相信你已经注意到了，堆排序和快速排序一样，其时间复杂度是 O(nlogn)，并且它非常稳定（这里的稳定指的是算法的性能，而不是上面说到的算法的稳定特性），在各种数据规模、数据排列特征下，它都能够保持 O(nlogn) 的运行时间，并且它还是原地排序。

但其实堆排序还是没有快速排序应用广泛，其中一个很重要的原因是堆排序无法利用 CPU 缓存，为什么这么说呢？

从上面堆排序的过程中，我们可以发现，其实堆排序在进行数据的构建堆操作时，一般不会顺序的读取数据，因为前面提到的那个公式，对于任意节点 i，其左子节点是 2 * i + 1，右子节点是 2 * i + 2。例如在数组下标为 3 处的节点，进行建堆时，会访问它的左右子节点，分别是 7 和 8，这对 CPU 缓存来说是不友好的。

后记

我本想将 Java 中内置的排序算法放到文章最后进行分析，但是 Java 里面的 DualPivotQuickSort 和 TimeSort 实在是有点复杂，并且加上这个的话文章的篇幅将会更长，所以以后可以针对这个单独写一篇文章，这次就暂时不介绍了。