快速排序

描述

众所周知，快速排序是一个复杂度较为低的排序，平均时间复杂度约n*log(n)，今天，我尝试对快速排序的本质做一些理解和复习。

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
#include <bits/stdc++.h>

using namespace std;
int  a[101], n;

void quicksort1(int left, int right){
        int i, j, t, temp;
        if(left > right)
                return;
        temp = a[left];//temp中存的就是基准数
        i = left;//左边界
        j = right;//右边界
        while(i != j){//当左右边界相等时，说明已经遍历完毕
                while(a[j] >= temp && i < j)//从右往左找到第一个小于temp的数
                        j--;//j--
                while(a[i] <= temp && i < j)//从左往右找到第一个大于temp的数
                        i++;
                if(i < j){//为何是i<j，因为i==j时，说明已经遍历完毕
                        t = a[i];//交换
                        a[i] = a[j];
                        a[j] = t;
                }
        }
        a[left] = a[i];
        a[i] = temp;
        quicksort1(left, i - 1);//
        quicksort1(i + 1, right);//递归

}

这是一开始的想法。取最左边的元素为基准点，然后j先动，直到找到小于基准点的那个元素；接着动i，直到找到大于基准点的那个元素；交换j,i的元素；像这个步骤顺序执行，直到任何一刻，i == j，然后，交换i位置和基准点位置的元素。这样就能达到基准点左侧的数小于基准点，基准点左侧的数大于基准点。然后，再调用递归，分别将基准点左侧和右侧修正为面向新基准点的类排序状态，直到这个调用结束。说实话，这有一点像深度优先搜索的例子。
但是，chatgpt告诉我，它有更好的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void quicksort(vector<int>& arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int pivot = arr[left];
    int i = left, j = right;
    while (i < j) {
        while (i < j && arr[j] >= pivot)
            j--;
        if (i < j) {
            arr[i++] = arr[j];
        }
        while (i < j && arr[i] <= pivot)
            i++;
        if (i < j) {
            arr[j--] = arr[i];
        }
    }
    arr[i] = pivot;
    quicksort(arr, left, i - 1);
    quicksort(arr, i + 1, right);
}

这是gpt的思路：它一开始就不打算将arr[left]保留至原位置。当j移动到小于基准点的位置，原来i位置的数会被j位置的覆盖；然后i移动到大于基准点的位置，j位置的数于是被i位置的覆盖。如此循环，仅仅a[left]是没有
被放进数列的。最后当i和j相遇，不管前面是什么情况，这个相遇位置的数一定已经被移动到它应该去的地方，于是在此处写入a[left]。然后也是调用递归。

思考

其实快速排序让我敬畏之许久，导致很长一段时间我都觉得这个排序很“迷”。为何？因为它的边界条件、特殊情况和执行顺序：

边界条件

a[left]是最大的数，且整个数列是逆序的，不就会执行非常多次？
确实，如果是逆序，那么是会执行n + (n-1) + (n-2) + … + 1 次，也就是冒泡排序的次数。

特殊情况/执行顺序

如果i从左至右能找到三个大于基准点的数，反之j从右至左能找到一个或者两个小于基准点的数，那么这个排序不就不成立了？这是我从一开始就很疑惑的点。不妨来举一个例子说清楚这个问题：
arr = {5, 6, 7, 8, 2 , 1}这个数组执行代码（第一种解法）过程中，1 和 6 会被先定位，然后交换arr = {5, 1, 7, 8, 2 , 6}，接着是2，7，arr = {5, 1, 2, 8, 7, 6}

接下来，就是这个排序的精华（起码我是这么认为的啦）了：永远先让j动——j移动到 “2” 的位置，与i重合。然后 5 和 2 交换，得到arr = {2, 1, 5, 8, 7, 6}，怎么样，不还是能跑嘛！

其实，j 先动，就能保证j右边的全是比 j 要大的，这是最重要的一环。

如果把 i 和 j 的移动顺序调换，上面的例子会变成arr = {8, 1, 2, 5, 7, 6}（ i 先到 8 的位置）。这样就不符合 5 左边的数都比 5 小的初衷了。因为，如果 i 先动，只能保证 i 左边的数会比 基准点 小，但是这个过程中一旦 i 和 j 碰面了，或者像这个例子，i右边且j左边没有小于基准点的数了，一定会让这个尴尬的位置非常棘手。究其根本的原因，
就是我们规定的是左小右大的排列顺序：最后一个和a[left]交换的一定不能大于基准点。所以，当j先动，不可避免地遇上了i，此时的i是先前被交换过来的那个 旧j位置的小于基准点的数，当然不怕和a[left]交换位置；
然而当i先动，若是不可避免地遇上了j，此时的j是先前被交换过来的那个 旧i位置的大于基准点的数，当然不能和a[left]交换位置，否则新的a[left]不就一定会>基准点咯！

反思

那么，如果左小右大，应该j先动，是不是说左大右小，就是i先动？让我们看下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void quicksort(vector<int>& arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int pivot = arr[left];
    int i = left, j = right;
    while (i < j) {
        while (i < j && arr[j] <= pivot)
            j--;
        if (i < j) {
            arr[i++] = arr[j];
        }
        while (i < j && arr[i] >= pivot)
            i++;
        if (i < j) {
            arr[j--] = arr[i];
        }
    }
    arr[i] = pivot;
    quicksort(arr, left, i - 1);
    quicksort(arr, i + 1, right);
}

这是gpt给的，当然经过验证是正确的代码。我们可以看到，用这种方式，我们确实可以做到左小右大。经过今天的分析，我们能得到一个结论：i和j的移动顺序和得到的数组的要求有密切的关系：要求 == 左小右大？ j 先动 : 要求 == 左大右小？ : i 先动 : 俺也不知道。
（容我写个嵌套三目结束今天的战斗！）