Yangsanity's Blog

Life was like a box of chocolates

0%

发表于 分类于 阅读次数： Disqus：

今天给大家带来一道 leetcode 的算法题。为什么这篇文章要写一道算法题？其实主要是想说之前写的排序算法可不只是为了面试用的。

这句话也算是一个小提示，那么你能不能与之前写的排序知识联系起来想到解法呢？

暴力

没啥好说的，一上来，两层 for 循环暴力枚举所有数对，逐一判断即可搞定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * 暴力法
 */
private int reversePairs(int[] nums) {
    // 逆序对总数
    int ret = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] > nums[j]) {
                ret++;
            }
        }
    }
    return ret;
}

结果当然可想而知，毕竟时间复杂度为 O(n^2)。此外空间复杂度为 O(1)。

归并排序

利用归并排序的思路解这道题，你想到了吗？

前面写归并排序的时候写过归并排序的思路，希望你还有印象（没印象的话可以点击文章底部链接去看看哦）。

其实解这道题我们只需要在 merge 操作上做些思考。还记得 merge 操作吧，它是要把两个有序数组合并成一个有序数组。而我们思考的方向，既可以在左边的有序数组上，也可以在右边的有序数组上，所以这个思路可以有两种写法。下面逐一说明。

在左边的有序数组上思考

假定待 merge 数组如下，记逆序对总数为 ret：

（1）8 < 9，不构成逆序对，此时 ret = 0

（2）12 > 9，构成逆序对，且左数组中 12 后边的数都和 9 构成逆序对，此时 ret = 3

（3）12 < 26，不构成逆序对，此时 ret = 3

（4）16 < 26，不构成逆序对，此时 ret = 3

（5）22 < 26，不构成逆序对，此时 ret = 3

（6）左数组遍历完，右数组剩下的元素入辅助数组。因为此时右数组剩下的值比原左数组的所有值都大，不会构成逆序对，所以这一轮 merge 的最终 ret = 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * 采用归并排序自底向上写法，具体可见归并排序文章
 * 当然也可以用自顶向下递归的方式来写，都是一样的，这部分其实也不是解题的重点
 */
public int reversePairs(int[] nums) {
    // ret 为逆序对总数
    int ret = 0, n = nums.length;
    if (n < 2) {
        return 0;
    }
    for (int i = 1; i < n; i *= 2) {
        for (int j = 0; j < n - i; j += 2 * i) {
            int mid = j + i - 1;
            if (nums[mid] > nums[j + i]) {
                ret += reversePairsHelper(nums, j, mid, Math.min(mid + i, n - 1));
            }
        }
    }
    return ret;
}

/**
 * “merge”考虑左数组
 */
private int reversePairsHelper(int[] nums, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0, ret = 0;
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            // 重点
            ret += mid - i + 1;
            temp[k++] = nums[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = nums[i++];
    }
    while (j <= right) {
        temp[k++] = nums[j++];
    }
    System.arraycopy(temp, 0, nums, left, temp.length);
    return ret;
}

在右边的有序数组上思考

要比在左数组思考多考虑一点点，不过也比较简单。

假定待 merge 数组如下，记逆序对总数为 ret：

（1）12 > 9，ret 不变，此时 ret = 0

（2）12 < 26，12 和右数组 26 之前的所有数构成逆序对，此时 ret = 1

（3）28 > 26，ret 不变，此时 ret = 1

（4）28 < 55，28 和右数组 55 之前的所有数构成逆序对，此时 ret = 3

（5）50 < 55，50 和右数组 55 之前的所有数构成逆序对，此时 ret = 5

（6）60 > 55，ret 不变，此时 ret = 5

（7）60 < 64，60 和右数组 64 之前的所有数构成逆序对，此时 ret = 8

（8）左数组遍历完，右数组剩下的元素入辅助数组。因为此时右数组剩下的值比原左数组的所有值都大，不会构成逆序对，所以这一轮 merge 的最终 ret = 8

注意，为什么说要比在左数组思考多考虑一点，就在这里。如果最后的情况是右数组遍历完，左数组剩下的元素入辅助数组。那么此时左数组剩下的值比原右数组的所有值都大，那么此时左数组剩下的值都和原右数组的所有值都能构成逆序对，这部分一定要计算在内！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * 代码同上
 * 采用归并排序自底向上写法，具体可见归并排序文章
 * 当然也可以用自顶向下递归的方式来写，都是一样的，这部分其实也不是解题的重点
 */
public int reversePairs(int[] nums) {
    // ret 为逆序对总数
    int ret = 0, n = nums.length;
    if (n < 2) {
        return 0;
    }
    for (int i = 1; i < n; i *= 2) {
        for (int j = 0; j < n - i; j += 2 * i) {
            int mid = j + i - 1;
            if (nums[mid] > nums[j + i]) {
                ret += reversePairsHelper(nums, j, mid, Math.min(mid + i, n - 1));
            }
        }
    }
    return ret;
}

/**
 * “merge”考虑右数组
 */
private int reversePairsHelper(int[] nums, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0, ret = 0;
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            // 重点
            ret += j - mid - 1;
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
        }
    }
    while (i <= mid) {
        // 重点
        ret += right - mid;
        temp[k++] = nums[i++];
    }
    while (j <= right) {
        temp[k++] = nums[j++];
    }
    System.arraycopy(temp, 0, nums, left, temp.length);
    return ret;
}

提交成功通过。时间复杂度同归并排序 O(n * logn)，空间复杂度也同归并排序 O(n)。

离散化树状数组

这个是从官方的解法中看到的，比较骚气，不过要用到一种新的数据结构 - 树状数组。

接下来说一下树状数组解这道题的思路吧，具体的树状数组和代码想放到下一篇再来写。

树状数组是一种可以动态维护数组前缀和的数据结构，它的主要功能是：

  1. 单点更新 update(i, v)：把序列 i 位置的数加上一个值 v，在这道题中 v = 1
  2. 区间查询 query(i)：查询序列 [1⋯i] 区间的区间和，即 i 位置的前缀和

其中单点更新和区间查询的时间复杂度都是 O(logn)，n 为需要维护前缀和的数组的长度。还要注意，树状数组中 0 索引位置是不参与计算的。（具体原因了解树状数组后就能理解）

假定数组 a 为 [5, 5, 2, 3, 6]，记逆序对总数为 ret。我们申请一个新数组，遍历 a，在新数组中记录 a 中每个值出现的次数，最终新数组结果如下：

index 0 1 2 3 4 5 6
value 0 0 1 1 0 2 1

可以看到，a[i] 的前缀和可以表示：a 数组中有多少个数比 a[i] 小。那么，如果 a[i] 之前的数在原数组中是出现在 a[i] 后面的，那么 i - 1 的前缀和就代表这些数和 a[i] 构成的逆序对数量。

明白了这一点，那就好做了。我们可以从后往前遍历 a，当遍历到 a[i] 时，把对应的新数组中 i 位置的值自增 1，然后再计算 i - 1 的前缀和，记到 ret 中。当 a 遍历完成后，ret 即为逆序对总数。

为什么可以这么做呢？因为我们在遍历 a 的过程中，把 a 分成了两部分，一部分遍历过（在新数组中），另一部分待遍历（不在新数组中）。那么对于 a[i] 来说，我们求到的 i - 1 位置的前缀和，就是遍历过的元素中比 a[i] 小的元素的总和，而这些元素在 a 中本来就是排在 a[i] 后面的，但它们的值是比 a[i] 小的，所以这就形成了一个逆序对。

离散化树状数组

确实像上面说的那么做是可以的，但是别忘了题目的限制：0 <= 数组长度 <= 50000，额，其实这个限制还好，内存中放得下。如果限制更大一点，内存中放不下怎么办呢？

其实，就算限制更大一点，大到内存中都放不下，但是给定的数组中肯定也是很多位置是 0，它的有效元素的位置是稀疏的。我们可以想办法让有效位置紧凑一点，减少无效位置的出现，减少空间浪费，这时我们就可以用到这个方法 - 离散化。

也就是说，我们只需要关心有效元素在数组中按大小的排名，来决定它们在数组中的位置即可。

恰好，java 里有一种数据结构可以做到去重并排序这一点，什么呢？就是 TreeSet。

离散化树状数组解这道题的思路大致就说完了。其实有个非常重要的点没有说，那就是：单点更新和区间查询的时间复杂度都是 O(logn) 这个是怎么做到的？如果明白了这一点，那么他为什么叫“树状数组”也就明白了。好了，写不少字了，卖个关子吧。

发表于 分类于 阅读次数： Disqus：

理解了上篇二叉堆的知识，堆排序（heap sort）就非常简单了。

堆排序代码

（会用到上一篇中 MaxHeap 类的代码）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 堆排序
 * @param data 待排序数组
 * @return 有序数组
 */
private int[] heapSort(int[] data) {
    int len = data.length;
    // 构建一个最大堆
    MaxHeap heap = new MaxHeap(len);
    for (int d : data) {
        heap.insert(d);
    }
    // 按顺序复制回原数组
    for (int i = len - 1; i >= 0; i--) {
        data[i] = heap.getMax();
    }
    return data;
}

堆排序优化代码

主要优化了上面代码中构建堆的方式。

上一篇说过，上面代码构建堆的时间复杂度是 O(nlogn)，我们可以把它优化到 O(n)。

（会用到上一篇中 MaxHeap 类的代码）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * 堆排序
 * @param data 待排序数组
 * @return 有序数组
 */
private int[] heapSort(int[] data) {
    int len = data.length;
    // 构建一个最大堆
    MaxHeap heap = new MaxHeap(data, len);
    // 按顺序复制回原数组
    for (int i = len - 1; i >= 0; i--) {
        data[i] = heap.getMax();
    }
    return data;
}

堆排序再优化

上面两种堆排序的代码都额外使用了 O(n) 的空间来创建堆，所以空间复杂度为 O(n)。

这个结果并不能让人满意，不过恰好还有一种更优的思路，可以应用最大堆的原理直接在原数组中进行排序，不需要任何额外的空间，将空间复杂度优化为 O(1)。

具体思路是：

  1. 一个数组本身就可以看做是一个堆，首先通过 Heapify 过程将它构建成一个最大堆；（数组长度记为 n）

  2. 此时，数组中的最大值就是当前第一个元素（记为 i），当整个数组排好序后，它的正确位置应该是数组末尾。所以把它和当前数组的末尾元素（记为 j）交换位置；

  3. 由于把 j 放到了数组第一个位置，此时，数组 [0, n - 1] 索引区间不再符合最大堆的性质，所以要把这个区间调整成最大堆。很简单，只需要在这个区间中对 j 做一次 shiftDown 操作就可以了；

  4. 此时，数组 [0, n - 1] 索引区间中的最大元素又在第一个位置了，之后再像之前一样操作。以此类推，直到整个数组都排好序。

可以发现，这个思路其实就是从上一篇中的 Heapify 和 shiftDown 算法来的。

堆排序再优化代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 堆排序
 * @param data 待排序数组
 * @return 有序数组
 */
private int[] heapSort(int[] data) {
    int len = data.length, temp;
    // 构建一个最大堆
    for (int i = (len - 2) / 2; i >= 0; i--) {
        shiftDown(data, len, i);
    }
    for (int i = len - 1; i > 0; i--) {
        // swap 0 and i
        temp = data[0];
        data[0] = data[i];
        data[i] = temp;
        shiftDown(data, i, 0);
    }
    return data;
}

/**
 * 优化后的 shiftDown，不用一直 swap
 * 具体可参考上一篇中的 shiftDown2 注释
 * @param data 待排序数组
 * @param len 待排序数组长度
 * @param i 当前要做 shiftDown 操作的数组索引位置
 */
private void shiftDown(int[] data, int len, int i) {
    int e = data[i];
    int il, ir;
    while ((il = 2 * i + 1) < len) {
        int j = il;
        if ((ir = j + 1) < len && data[ir] > data[j]) {
            j = ir;
        }
        if (e >= data[j]) {
            break;
        }
        data[i] = data[j];
        i = j;
    }
    data[i] = e;
}

复杂度和稳定性分析

  1. 时间复杂度

构建最大堆时间复杂度为 O(n)，每个元素做一次 shiftDown 操作时间复杂度为 O(logn)，所以整体的时间复杂度为 O(n * logn)。

  • 最优时间复杂度：O(n * logn)

  • 最坏时间复杂度：O(n * logn)

  • 平均时间复杂度：O(n * logn)

  1. 空间复杂度：O(1)
  • 原地堆排序，不需要额外的辅助空间。
  1. 堆排序是一种不稳定排序。
  • 很好举例，假如待排序数组为 [9, 8, 8]。

发表于 分类于 阅读次数： Disqus：

按进度应该是要写堆排序的，所以这篇文章先来介绍一下堆（Heap）。

对于堆排序来说，排序反而是次要的，解决排序问题只是堆这种数据结构衍生出来的一个应用而已。

除此之外，堆还能衍生出来一个重要的数据结构-优先队列（Priority Queue），不过这个得后面再说。今天主要介绍堆的一种经典实现-二叉堆（Binary Heap）。

堆是树形结构，所以先简单复习几个树的概念。（只是解释二叉堆需要用到的几个概念而已）

二叉堆的形式

树（Tree）也是一种数据结构。二叉树（Binary Tree）是树的一种形式，二叉意味着每个节点最多只有两个孩子节点-左孩子结点和右孩子结点，当然“最多”这两个字也意味着，每个节点可以只有一个孩子节点或者没有孩子节点。从这个定义可以看出来，一个节点也可以称为一棵二叉树。

二叉树

从图中可以看到两个规律：

  1. 二叉树的第 i 层至多拥有 2^(i - 1) 个节点；
  2. 深度为 h 的二叉树至多总共有 2^h - 1 个节点（根节点所在深度 0）。

二叉树有两种特殊形式，一种叫满二叉树（Full binary tree），一种叫完全二叉树（Complete Binary Tree）。

结合上面的规律，深度为 h 且节点总数为 2^h - 1 的二叉树为满二叉树。说直白点就是，如果一棵二叉树的所有非叶子节点都有左右孩子，并且所有叶子节点都在最后一层，则该二叉树为满二叉树。

满二叉树

如果一棵二叉树除了最后一层节点之外，其它各层的节点个数都达到最大值，且最后一层的所有叶子节点是从左到右依次排布，则该二叉树为完全二叉树。

完全二叉树

说了这么多，就为了这一句：二叉堆本质上就是一颗完全二叉树。

二叉堆的类型

二叉堆可以分为两个类型：最大堆（大顶堆）和最小堆（小顶堆）。

二叉堆的根节点称为堆顶。最大堆中任何一个父节点的值都大于或等于它的左右孩子的节点的值；同理可得，最小堆中任何一个父节点的值都小于或等于它的左右孩子的节点的值。因此最大堆的堆顶元素是整个堆中的最大元素；最小堆的堆顶元素是整个堆中的最小元素。

但是有一点要强调一下，最大堆不意味着层数高的节点的数值一定大于层数低的节点的数值；最小堆也不意味着层数高的节点的数值一定小于层数低的节点的数值。

最大堆

本文下面所有内容都以最大堆为例，最小堆可以留作大家的思考。

二叉堆（最大堆）的调整

二叉堆的调整一般有三种操作。

Shift Up（上浮）

向堆中插入一个元素。以上图中的堆插入一个新的元素 20 为例。插入位置为完全二叉树的最后一个位置。

此时显然不符合最大堆的性质，所以对新插入节点做 Shift Up 操作：即用新插入节点的值和它父节点的值进行比较，如果大于父节点的值，则和父节点交换位置。

此时，发现还是不符合最大堆的性质，继续 Shift Up，直到满足最大堆的性质为止。

Shift Down（下沉）

从堆中删除一个元素。以上图中的堆删除一个元素为例。注意删除的元素只能是堆顶元素，此时，要把堆中的最后一个节点临时补到堆顶。

此时显然不符合最大堆的性质，所以对堆顶节点做 Shift Down 操作：即用堆顶节点的值和它左右孩子节点值中最大的一个（记为 p）进行比较，如果小于 p 节点的值，则和 p 节点交换位置。

此时，发现还是不符合最大堆的性质，继续 Shift Down，直到满足最大堆的性质为止。

Heapify

将给定数组堆化，将数组变成一个最大堆。

这里先放一放，等了解完二叉堆的存储再来说 Heapify 的具体操作。

二叉堆（最大堆）的存储

既然二叉堆是一颗二叉树，那么它的代码实现自然是可以用常规的树的代码来实现。但是其实二叉堆的经典实现方式是数组。为什么可以用数组呢？正是因为二叉堆是一颗完全二叉树。我们把二叉树的节点值，按照自上到下，自左到右的顺序存到数组中。

一种经典的实现如下图所示：

最大堆及其存储

可以看到我们从数组中的第二个索引位置开始放置元素，那么此时如何定位父节点和孩子节点之间的关系呢？可以依靠数组下标来计算。

这种实现的好处就是，节点之间的规律比较容易发现。假设 p 节点在数组中的索引位置为 i，那么对于 p 节点来说：

  1. parent(p) = i / 2
  2. leftChild(p) = 2 * i
  3. rightChild(p) = 2 * i + 1

但是这种实现会浪费索引为 0 的位置的空间，这简直是要逼死完美主义者（强迫症…）。所以这种实现思路就不给出具体的代码了，大家可以自己写一下。

其实我们也完全可以从 0 索引位置开始来存储，但是在规律上我们需要做一个大小为 1 的偏移量。

最大堆及其存储

此时的规律，假设 p 节点在数组中的索引位置为 i，那么对于 p 节点来说：

  1. parent(p) = (i - 1) / 2
  2. leftChild(p) = 2 * i + 1
  3. rightChild(p) = 2 * i + 2

再来说 Heapify

说到这里，我们再来想想，如何将给定数组堆化（最大堆）？

一个特别直观的思路就是，遍历这个数组，将每个元素都做 Shift Up 即可。在这个操作中，每个元素都要遍历一次，每次 Shift Up 都需要 logn 的时间，假设数组元素个数为 n，那么总的时间复杂度是 O(nlogn)。

其实 O(nlogn) 的时间复杂度已经非常不错了，但是其实还有一种更优的思路，只需要 O(n) 的时间复杂度。

这个思路就是，从最大堆的最后一个非叶子节点开始，向前遍历数组，每个元素依次做 Shift Down 操作即可。因为对于每个叶子节点来说，它们是符合最大堆的性质的。

从最后一个非叶子节点开始向前遍历

这个思路的时间复杂度可能不太好证明，但是直观上来看，我们要将数组构建成最大堆，一上来就舍弃了数组中几乎一半的元素，那么速度肯定会更快。

现在唯一的问题就是最大堆的最后一个非叶子节点在数组中的索引是多少？不难发现，它的 index = (最后一个节点索引值 - 1) / 2。假设数组元素个数为 n，即 index = (n - 1 - 1) / 2 = (n - 2) / 2。

二叉堆（最大堆）代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
/**
 * 二叉堆，最大堆
 */
public class MaxHeap {

    /**
     * 二叉堆中存储的元素
     */
    private int[] data;

    /**
     * 二叉堆中存储的元素数量
     */
    private int count;

    /**
     * 二叉堆容量
     */
    private int capacity;

    public MaxHeap(int capacity) {
        this.data = new int[capacity];
        this.count = 0;
        this.capacity = capacity;
    }

    public MaxHeap(int[] data) {
        this(data, data.length);
    }

    public MaxHeap(int[] data, int len) {
        this.data = new int[len];
        this.capacity = len;
        this.count = len;
        System.arraycopy(data, 0, this.data, 0, data.length);
        // 从最后一个非叶子节点开始 shiftDown
        for (int i = (len - 2) / 2; i >= 0; i--) {
            shiftDown2(i);
        }
    }

    /**
     * 返回堆中的元素个数
     * @return 堆中的元素个数
     */
    public int size() {
        return count;
    }

    /**
     * 返回一个布尔值, 表示堆中是否为空
     * @return true 表示堆为空
     */
    public boolean isEmpty() {
        return count == 0;
    }

    /**
     * 堆中插入一个元素
     * @param i 插入的元素
     */
    public void insert(int i) {
        // todo 此处可以实现为动态扩容，会更友好些，大家可以自己去实现
        assert this.count < this.capacity;
        // 插入位置为堆的最后一个位置
        this.data[this.count] = i;
        // 对新插入节点做 shiftUp
        shiftUp2(this.count);
        this.count++;
    }

    private void shiftUp(int i) {
        // i 父节点的索引
        int ip;
        // i 不是根节点 && i 的父节点的值 < i 节点的值
        while (i > 0 && this.data[ip = (i - 1) / 2] < this.data[i]) {
            swap(i, ip);
            i = ip;
        }
    }

    // 优化 shiftUp，不一直swap
    private void shiftUp2(int i) {
        int e = this.data[i];
        // i 父节点的索引
        int ip;
        // i 不是根节点 && i 的父节点的值 < i 节点的值
        while (i > 0 && this.data[ip = (i - 1) / 2] < e) {
            this.data[ip] = this.data[i];
            i = ip;
        }
        this.data[i] = e;
    }

    /**
     * 获取堆中的最大值（从堆中删除一个元素）
     * @return 堆中最大值
     */
    public int getMax() {
        // todo 此处可以实现为动态扩容，会更友好些，大家可以自己去实现
        assert this.count >= 0;
        int ret = this.data[0];
        // 把堆中的最后一个节点临时补到堆顶
        swap(0, this.count - 1);
        this.count --;
        // 对新的堆顶节点做 shiftDown
        shiftDown2(0);
        return ret;
    }

    private void shiftDown(int i) {
        // il 代表 i 节点的左孩子节点索引；ir 代表 i 节点的右孩子节点索引
        int il, ir;
        // while (i 节点有左孩子)
        while ((il = 2 * i + 1) < this.count) {
            // j 是 i 节点的两个孩子节点中最大值的索引，初始值为左孩子的索引
            int j = il;
            // 如果 i 节点还有右孩子 且 右孩子的值大于左孩子的值，j 更新为右孩子的索引
            if ((ir = j + 1) < this.count && this.data[ir] > this.data[j]) {
                j = ir;
            }
            // 此时 data[j] 是 i 节点的两个孩子节点中的最大值
            // 如果 i 节点的值大于等于 data[j]，结束循环
            if(this.data[i] >= this.data[j]) {
                break;
            }
            swap(i, j);
            // 为下次循环做准备
            i = j;
        }
    }

    // 优化 shiftDown，不一直swap
    private void shiftDown2(int i) {
        int e = this.data[i];
        int il, ir;
        while ((il = 2 * i + 1) < this.count) {
            int j = il;
            if ((ir = j + 1) < this.count && this.data[ir] > this.data[j]) {
                j = ir;
            }
            if(e >= this.data[j]) {
                break;
            }
            this.data[i] = this.data[j];
            i = j;
        }
        this.data[i] = e;
    }

    /**
     * 交换堆数组中 i 和 j 索引位置的值
     * @param i 待交换索引
     * @param j 待交换索引
     */
    private void swap(int i, int j) {
        int temp = this.data[i];
        this.data[i] = this.data[j];
        this.data[j] = temp;
    }
}

（上面的代码中有两个小的优化，shiftUp2 和 shiftDown2，你看到了吗？）

凑字数

理解了二叉堆，堆排序就非常容易了，下一篇就可以直接开撕。

发表于 分类于 阅读次数： Disqus：

快排完结篇终于来了。

从上篇遗留问题说起

接着上篇最后留下的问题说：当待排序数组有非常多的重复值时，随着数据量增大，快排此时依然会退化到最坏时间复杂度 O(n^2)。为什么呢？

仍然从快排递归生成的递归树来考虑。当待排序数组有非常多的重复值时，上篇单路快排的 partition 操作还是会把整个数组分成极度不平衡的两部分。因为单路快排的 partition 方式会把等于基准值的数都放在基准值的某一边（左边或者右边）。如果待排序数组有大量重复元素，此时无论选择的基准值是什么，都会导致生成的递归树严重往一边倾斜。这种情况下，快排当然又会退化到最坏时间复杂度 O(n^2)。

双路快速排序思路

解决方案一：用双路快排的方式来重写 partition。

接下来用个简单的demo来演示一下整个过程吧。这里仍然规定直接简单选取数组第一个元素作为基准值，待排序数组如下：

5 3 9 5 2 4 5 8 1

首先我们必须定义几个变量来辅助我们理解整个过程。如下图，定义 pivot 为基准值；i 为从左往右正在遍历的元素；j 为从右往左正在遍历的元素。

在整个遍历过程中，要一直保证 [left + 1, i - 1] 区间的元素都是小于等于基准值的，[j + 1, right] 区间的元素都是大于等于基准值的。

partition 过程为：

先从 i 开始向后扫描（或者，也可以先从 j 开始向前扫描），如果还没有遍历到 right 位置且当前值小于基准值，则不处理，继续查看下一个元素，直到找到一个值大于等于基准值；
这时从 j 开始向前扫描，如果还没有遍历到 left + 1 位置且当前值大于基准值，则不处理，继续查看下一个元素，直到找到一个值小于等于基准值；
此时，如果 i <= j，则交换 i 和 j 位置的值，之后 i 和 j 再分别指向下一个元素；否则跳出循环；
跳出循环后，现在应该把基准值放到合适的位置。那么这个位置是 i 还是 j 呢？分析一下：此时 i 的位置，是从前往后第一个大于等于基准值的元素；此时 j 的位置，是从后往前第一个（也就是从前往后最后一个）小于等于基准值的元素；而基准值是处在小于等于基准值的这一端，所以要将 pivot 和 j 位置的值进行交换即可。

第一轮 partition 的详细过程为：
（1）i：3 < 5，保持不变；9 > 5，停止；
j：1 < 5，停止；
i 和 j 位置的值进行交换，即 9 和 1 进行交换

（2）i：5 = 5，停止；
j：8 > 5，保持不变；5 = 5，停止；
i 和 j 位置的值进行交换，即 5 和 5 进行交换（不要觉得这步多余哦）

（3）i：2 < 5，保持不变；4 < 5，保持不变；5 = 5，停止；
j：4 < 5，停止；
此时 i > j，结束整个遍历过程

（4）遍历结束，把 pivot 和 j 位置的值进行交换，即 5 和 4 进行交换。此时，数组中所有小于等于 5 的元素都在它的左边，所有大于等于 5 的元素都在它的右边

4 3 1 5 2 5 5 8 9
（5）接下来只需要对 [4, 3, 1, 5, 2] 和 [5, 8, 9] 分别进行递归处理即可

第二步的最后，括号中写了不要觉得这一步多余，但是按理说，5 和 5 相等，交换也没有什么意义，直接跳过还能节省交换的时间，那么为什么还要进行交换呢？

从上一篇中我们知道，我们必须要保证排序过程中递归生成的递归树尽量平衡，才能避免快排的时间复杂度退化到 O(n^2)。第二步的交换操作正是为了这个原因。

举个例子，假如待排序数组为 [0, 0, 0, 0, 0, 1, 0, 0, 0, 0]，如果 i 和 j 指向的 0 不进行交换，那么第一轮 partition 的结果是数组的第一个位置；如果交换，那么第一轮 partition 的结果是 4。可以看到，如果相同值不进行交换，会导致递归树平衡度不够好，从而影响排序性能。

双路快速排序代码

这里给出的代码也直接应用了上篇中提到的两个优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/**
 * quickSort双路快排
 * @param data 待排序的数组
 */
public void quickSort(int[] data) {
    quickSortHelper(data, 0, data.length - 1);
}

/**
 * 递归使用双路快排排序
 * @param data 待排序的数组
 * @param left 起始位置
 * @param right 结束位置
 */
private static void quickSortHelper(int[] data, int left, int right) {
    // 优化1：对于小规模数组（这里指定为16个元素）, 使用插入排序
    if(right - left <= 15){
        insertSort(data, left, right);
        return;
    }
    int pivot = partition(data, left, right);
    // 递归排序基准数左部分
    quickSortHelper(data, left, pivot - 1);
    // 递归排序基准数右部分
    quickSortHelper(data, pivot + 1, right);
}

/**
 * 对数组 [left, right] 部分进行 partition 操作，双路
 * @param data 待排序的数组
 * @param left 起始位置
 * @param right 结束位置
 * @return 返回基准值位置，保证 data[left...pivot - 1] < data[pivot]; data[pivot + 1...right] > data[pivot]
 */
private static int partition(int[] data, int left, int right) {
    // 优化2：随机在 data[left...right] 范围中, 选择一个位置作为基准值
    int randomIndex = (int) (Math.random() * (right - left + 1)) + left;
    int temp = data[left];
    data[left] = data[randomIndex];
    data[randomIndex] = temp;
    // pivot，i，j 的定义在上边已经介绍
    int pivot = data[left], i = left + 1, j = right;
    while (true) {
        while (i <= right && data[i] < pivot) {
            i++;
        }
        while (j >= left + 1 && data[j] > pivot) {
            j--;
        }
        if (i > j) {
            break;
        }
        // swap i and j
        temp = data[i];
        data[i] = data[j];
        data[j] = temp;
        i ++;
        j --;
    }
    // swap left and j
    data[left] = data[j];
    data[j] = pivot;
    return j;
}

/**
 * 为了方便大家观看，这个插入排序的代码是直接从上一篇中拿过来的
 * 对data[l...r]的区间使用插入排序
 * @param data 待排序数组
 * @param l 起始index，代表left
 * @param r 结尾index，代表right
 */
private static void insertSort(int[] data, int l, int r) {
  for( int i = l + 1 ; i <= r ; i ++ ){
    int e = data[i];
    int j = i;
    for (; j > l && data[j-1] > e; j--) {
      data[j] = data[j - 1];
    }
    data[j] = e;
  }
}

双路快速排序总结

回到最初的问题，我们再来分析一下为什么双路快排可以解决大量重复元素的问题。

对比上篇单路快排，双路快排的 partition 方式会把等于基准值的元素分散放在基准值的两边（左边和右边），所以生成的递归树平衡度就会好很多。因此在大量重复值的情况下，双路快排能够防止时间复杂度退化到 O(n^2)。

三路快速排序思路

解决方案二：用三路快排的方式来重写快排。

接下来用个简单的demo来演示一下整个过程吧。这里仍然规定直接简单选取数组第一个元素作为基准值，待排序数组如下：

5 3 9 5 2 4 5 8 1

同样，首先我们必须定义几个变量来辅助我们理解整个过程。如下图，定义 pivot 为基准值；i 为从左往右正在遍历的元素；lt（less than） 为小于基准值部分的最后一个元素；gt（greater than） 为大于基准值部分的第一个元素。

在整个遍历过程中，要一直保证 [left + 1, lt] 区间的元素都是小于基准值的，[gt, right] 区间的元素都是大于基准值的，[lt + 1, i - 1] 区间的元素都是等于基准值的，[i, gt) 是 i 要扫描的区间。

partition 过程为：

从 i 开始向后扫描，如果还没有遍历到 gt 位置，且当前值等于基准值，则不处理，继续查看下一个元素；
如果还没有遍历到 gt 位置，且当前值小于基准值，则交换 i 和 lt + 1 位置的值；然后 i 和 lt 都指向下一个元素；
如果还没有遍历到 gt 位置，且当前值大于基准值，则交换 i 和 gt - 1 位置的值；然后 gt 指向下一个元素。注意此时 i 是不用动的；
i 遍历结束后，再把 pivot 和 lt 位置的值进行交换即可。

第一轮 partition 的详细过程为：
（1）3 < 5，i 和 lt + 1 位置的值进行交换，即 3 不用动；然后 i 和 lt 都指向下一个元素

（2）9 > 5，i 和 gt - 1 位置的值进行交换，即 9 和 1 进行交换；然后 gt 指向下一个元素（注意此时 i 不用动）

（3）（不要忘了 i 没有动）1 < 5，i 和 lt + 1 位置的值进行交换，即 1 不用动；然后 i 和 lt 都指向下一个元素

（4）5 = 5，保持不变；2 < 5，i 和 lt + 1 位置的值进行交换，即 2 和 5 进行交换；然后 i 和 lt 都指向下一个元素

（5）4 < 5，i 和 lt + 1 位置的值进行交换，即 4 和 5 进行交换；然后 i 和 lt 都指向下一个元素；5 = 5，保持不变

（6）遍历结束，把 pivot 和 lt 位置的值进行交换，即 5 和 4 进行交换。此时，数组中所有等于 5 的元素都位于数组中间，所有小于 5 的元素都在数组左边，所有大于 5 的元素都在数组右边

4 3 1 2 5 5 5 8 9
（7）接下来只需要对 [4, 3, 1, 2] 和 [8, 9] 分别进行递归处理即可

三路快速排序代码

这里给出的代码也直接应用了上篇中提到的两个优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/**
 * quickSort三路快排
 * @param data 待排序的数组
 */
private void quickSort(int[] data) {
    quickSortHelper(data, 0, data.length - 1);
}

/**
 * 递归使用三路快排排序
 * 直接包含了对数组 [left, right] 部分进行 partition 操作的代码
 * @param data 待排序的数组
 * @param left 起始位置
 * @param right 结束位置
 */
private static void quickSortHelper(int[] data, int left, int right) {
    // 优化1：对于小规模数组（这里指定为16个元素）, 使用插入排序
    if (right - left <= 15) {
        insertSort(data, left, right);
        return;
    }
    /* partition start */
    // 优化2：随机在 data[left...right] 范围中, 选择一个位置作为基准值
    int randomIndex = (int) (Math.random() * (right - left + 1)) + left;
    int temp = data[left];
    data[left] = data[randomIndex];
    data[randomIndex] = temp;
    // pivot，i，lt，gt 的定义在上边已经介绍
    int pivot = data[left], lt = left, gt = right + 1, i = left + 1;
    while (i < gt) {
        if (data[i] < pivot) {
            // swap i and lt + 1
            temp = data[i];
            data[i] = data[lt + 1];
            data[lt + 1] = temp;
            i ++;
            lt ++;
        } else if (data[i] > pivot) {
            // swap i and gt - 1
            temp = data[i];
            data[i] = data[gt - 1];
            data[gt - 1] = temp;
            gt --;
        } else {
            // if (data[i] == pivot)
            i ++;
        }
    }
    // swap left and lt
    data[left] = data[lt];
    data[lt] = pivot;
    /* partition end */
    // 递归排序数组左部分
    quickSortHelper(data, left, lt - 1);
    // 递归排序数组右部分
    quickSortHelper(data, gt, right);
}

/**
 * 为了方便大家观看，这个插入排序的代码是直接从上一篇中拿过来的
 * 对data[l...r]的区间使用插入排序
 * @param data 待排序数组
 * @param l 起始index，代表left
 * @param r 结尾index，代表right
 */
private static void insertSort(int[] data, int l, int r) {
  for( int i = l + 1 ; i <= r ; i ++ ){
    int e = data[i];
    int j = i;
    for (; j > l && data[j-1] > e; j--) {
      data[j] = data[j - 1];
    }
    data[j] = e;
  }
}

三路快速排序总结

为什么我们这次不是重写 partition，而是直接把 partition 的部分写在了 quickSortHelper 里呢？

相信大家也都明白了，对于三路快排的 partition 来说，不只是简单的返回索引位置，每次 partition 结束后中间部分都是一个区间，这就导致没办法把 partition 部分的代码再单独设计成一个函数了。

其实解决大量重复元素最经典的方式就是三路快排，这种方式在大量重复值的情况下效率更高。因为对比双路快排，三路快排会把数组分成小于基准值、等于基准值和大于基准值三部分，这样在每次 partition 结束后，等于基准值的部分就已经放到了数组正确的位置，在后续递归过程中这部分就不用再处理了，只需要再递归处理小于基准值和大于基准值的部分即可。

可以看到三路快排的优点是不需要对大量等于基准值的元素进行重复操作，如果等于基准值的元素非常多，在后续递归过程中就可以一次性少处理很多元素。所以在大量重复值的情况下，这个优化会非常明显。

复杂度和稳定性分析

  1. 时间复杂度

  • 最优时间复杂度：O(n * logn)

    • 分析过程可以类似于归并排序，都是分治法。

  • 最坏时间复杂度：O(n^2)

  • 平均时间复杂度：O(n * logn)

  1. 空间复杂度：O(logn) ~ O(n)
  • 我们的快排代码是通过递归调用实现的，所以需要一个栈空间来辅助递归。最好情况下，类似于归并排序，所需栈的最大深度为 logn；最坏情况下，所需栈的最大深度为 n。所以，快排的空间复杂度为 O(logn) ~ O(n)。
  1. 快速排序是一种不稳定排序。
  • 上面双路快排的 demo 已经能够说明。

凑字数

到此为止，终于把快排分析完了。感谢你看到了这里，希望文章能够对你有些帮助。如果再遇到快排相关面试的话，希望你能够侃侃而谈。

发表于 分类于 阅读次数： Disqus：

快速排序（quick sort）又称分区交换排序（partition-exchange sort），简称快排。它的鼎鼎大名，在排序界无人不知，无人不晓，重要性更是无需多言。毕竟敢叫这么直白的名字，那“实力”肯定也是没话讲的。

快排还有一个响亮的 title，它被称为20世纪对世界影响最大的算法之一。当然，它必须也是面试中算法的一个高频考察点。（必须要再次提到面试，原因你懂的）

我猜你可能知道单路快排，那么你知道还有双路快排吗？甚至三路快排吗？知道如何优化快排吗？废话不多说，赶快上车。

快速排序思想

和归并排序一样，快排也是使用了分治法（Divide and Conquer）的思想，把一个待排序数组以基准值为界，分为两个子数组，左边都比基准值小，右边都比基准值大，然后再递归地对两个子数组进行排序。

快排大概可以分为三个步骤：

  1. 从当前待排序的数组中选择一个元素作为基准值（pivot）；

  2. 把基准值移动到当数组排好序时它应该处于的正确位置上，并且使得数组中所有比基准值小的元素放在基准值左边，所有比基准值大的元素放在基准值右边（与基准值相等的数可以到任何一边）。这个操作一般称为 partition；

  3. 对基准数左边数组和右边数组再分别继续使用相同的思路进行排序，逐渐递归下去，直到完成整个排序过程。

单路快速排序思路

接下来用个简单的demo来演示一下整个过程吧。这里先规定直接简单选取数组第一个元素作为基准值，待排序数组如下：

5 8 2 4 7 9 1 6 3

首先我们必须定义几个变量来辅助我们理解整个过程。如下图，定义 pivot 为基准值；i 为当前正在遍历的元素；j 为小于基准值的区域边界。

在整个遍历过程中，要一直保证 [left + 1, j] 区间的元素都是小于基准值的，[j + 1, i - 1] 区间的元素都是大于等于基准值的（这里把等于基准值的元素放到了 [j + 1, i - 1] 区间中，当然也可以放到 [left + 1, j] 区间中）。所以在遍历的过程中，只有当 i 当前指向的值小于 pivot 时，我们才需要把当前 i 位置的值和 j + 1 位置的值进行交换；当遍历完成时，再把 pivot 和 j 位置的值进行交换即可。

第一轮 partition 的详细过程为：

（1）8 > 5，保持不变；2 < 5，i 和 j + 1 位置的值进行交换，即 2 和 8 进行交换

（2）4 < 5，i 和 j + 1 位置的值进行交换，即 4 和 8 进行交换

（3）7 > 5，保持不变；9 > 5，保持不变；1 < 5，i 和 j + 1 位置的值进行交换，即 1 和 8 进行交换

（4）6 > 5，保持不变；3 < 5，i 和 j + 1 位置的值进行交换，即 3 和 7 进行交换

（5）此时，遍历完成，把 pivot 和 j 位置的值进行交换，即 5 和 3 进行交换。此时，数组中所有比 5 小的元素都在它的左边，所有比 5 大的元素都在它的右边

3 2 4 1 5 9 8 6 7
（6）接下来，对 5 左右两边的数组再分别继续使用相同的方法进行排序，直到完成整个排序过程。

注：上面是从左到右使用单路快排的思路，为了开拓思维，当然也可以使用从右到左单路快排的思路。

单路快速排序代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * quickSort单路快排
 * @param data 待排序的数组
 */
public void quickSort(int[] data) {
  quickSortHelper(data, 0, data.length - 1);
}

/**
 * 递归使用单路快排排序
 * @param data 待排序的数组
 * @param left 起始位置
 * @param right 结束位置
 */
private static void quickSortHelper(int[] data, int left, int right) {
  if (left >= right) {
      return;
  }
  int pivot = partition(data, left, right);
  // 递归排序基准数左部分
  quickSortHelper(data, left, pivot - 1);
  // 递归排序基准数右部分
  quickSortHelper(data, pivot + 1, right);
}

/**
 * 对数组 [left, right] 部分进行 partition 操作，从左往右单路
 * @param data 待排序的数组
 * @param left 起始位置
 * @param right 结束位置
 * @return 返回基准值位置，保证 data[left...pivot - 1] < data[pivot]; data[pivot + 1...right] > data[pivot]
 */
private static int partition(int[] data, int left, int right) {
  // pivot，i，j的定义在上边已经介绍
  int pivot = data[left], j = left, temp;
  for (int i = left + 1 ; i <= right; i ++) {
      if (data[i] < pivot) {
          j++;
          // swap i and j + 1
          temp = data[j];
          data[j] = data[i];
          data[i] = temp;
      }
  }
  // swap left and j
  data[left] = data[j];
  data[j] = pivot;
  return j;
}

单路快速排序优化

首先第一个优化相信大家看了上一篇归并排序优化的话肯定能想到，那就是当递归到数据量比较小时，转而使用插入排序提高性能。

除此之外，其实这里还有一个非常重要的问题：如果当待排序数组是近乎有序或者完全有序的情况下，会发生什么事情？

大家可以在自己的 ide 上测试一下，会发现，当随着数据量增大，快排会越来越慢。这是为什么呢？

我们对比着归并排序来分析一下。归并排序和快速排序都是使用的分治法的思想，都是要把待排序数组一分为二，不同的是，归并排序能保证每次都是把数组平均一分为二，而快排是以基准值一分为二，所以一般情况下，快排分出来的子数组都是一大一小的。

所以对于两者递归生成的递归树，归并排序的平衡度要更好，并且可以保证递归树的高度为logn，而快排生成的递归树高度非常有可能要比logn高。最差情况就是当整个待排序数组本来就近乎有序或者完全有序时，此时快排的时间复杂度会退化到最坏的时间复杂度 O(n^2)。

一句话概括造成这种情况的原因，就是基准值选的不够好。不能简单粗暴的直接选数组中第一个值作为基准值，我们希望的最好情况是能够选择数组排好序时中间的元素作为基准值。可是这个值又不好准确的定位，其实，我们只需要在数组中随机选择一个元素即可。

在这种情况下，快排的时间复杂度退化为 O(n^2) 的可能性是非常非常低的，几乎为 0。

具体在代码优化实现上，我们只需要在上边 partition 代码开始时加一行代码，把 left 和随机位置的值进行交换即可，后边的代码都不用动。

单路快速排序优化代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/**
 * quickSort单路快排优化
 * @param data 待排序的数组
 */
public void quickSort(int[] data) {
  quickSortHelper(data, 0, data.length - 1);
}

/**
 * 递归使用单路快排排序
 * @param data 待排序的数组
 * @param left 起始位置
 * @param right 结束位置
 */
private static void quickSortHelper(int[] data, int left, int right) {
    // 优化1：对于小规模数组（这里指定为16个元素）, 使用插入排序
    if(right - left <= 15){
        insertSort(data, left, right);
        return;
    }
    int pivot = partition(data, left, right);
    // 递归排序基准数左部分
    quickSortHelper(data, left, pivot - 1);
    // 递归排序基准数右部分
    quickSortHelper(data, pivot + 1, right);
}

/**
 * 对数组 [left, right] 部分进行 partition 操作，从左往右单路
 * @param data 待排序的数组
 * @param left 起始位置
 * @param right 结束位置
 * @return 返回基准值位置，保证 data[left...pivot - 1] < data[pivot]; data[pivot + 1...right] > data[pivot]
 */
private static int partition(int[] data, int left, int right){
    // 优化2：随机在 data[left...right] 范围中, 选择一个位置作为基准值
    int randomIndex = (int) (Math.random() * (right - left + 1)) + left;
    int temp = data[left];
    data[left] = data[randomIndex];
    data[randomIndex] = temp;
    // 下面逻辑完全不变
    // pivot，i，j的定义在上边已经介绍
    int pivot = data[left], j = left;
    for (int i = left + 1 ; i <= right; i ++) {
        if (data[i] < pivot) {
            j++;
            // swap i and j + 1
            temp = data[j];
            data[j] = data[i];
            data[i] = temp;
        }
    }
    // swap left and j
    data[left] = data[j];
    data[j] = pivot;
    return j;
}

/**
 * 为了方便大家观看，这个插入排序的代码是直接从上一篇中拿过来的
 * 对data[l...r]的区间使用插入排序
 * @param data 待排序数组
 * @param l 起始index，代表left
 * @param r 结尾index，代表right
 */
private static void insertSort(int[] data, int l, int r) {
  for( int i = l + 1 ; i <= r ; i ++ ){
    int e = data[i];
    int j = i;
    for (; j > l && data[j-1] > e; j--) {
      data[j] = data[j - 1];
    }
    data[j] = e;
  }
}

单路快速排序总结

到此为止，我们的快排已经能够完美解决随机数组和几乎有序数组的排序问题。

可以看到，为了避免快排的时间复杂度退化为最坏的时间复杂度 O(n^2)，我们实际上是用随机函数来编写了一个随机化算法（randomized algorithm）。也就是说，我们不能保证我们的算法是一定非常快的，但是可以保证我们的算法在非常非常高的概率下都能非常快。

为什么还有双路、三路快排？

我们的代码完美了吗？当然还不够，因为还是忽略了一种情况：如果当待排序数组有非常多的重复值时，会发生什么事情？

大家仍然可以在自己的 ide 上测试一下，会发现，当随着数据量增大，快排依然会越来越慢，说明此时快排又退化到了最坏时间复杂度 O(n^2)。这又是为什么呢？

当然小标题已经暴露了解决方案，大家可以自己先想想，分析一下。

因为已经写的够长啦，大家可以先消化一下，欲知后事如何且听下回分解…