Notepad

快速排序讲解

快速排序$\ (Quick\ Sort)\ $，是一种高效且复杂度相对稳定的排序算法，在一定优化之后更可以达到绝大多数情况下$\ O(n\ log\ n)\ $的时间复杂度和不超$\ O(log\ n)\ $的空间复杂度

原理

快速排序的实现基于分治思想：

每次将原数组分割为两个子数组，保证左子数组中任一元素都小于右子数组中任一元素，然后递归处理两个子数组直到数组只剩一个元素，从而完成对整个数组的排序

具体实现

1. 划分数组为两个子数组

2. 递归继续划分两个子数组

3. 子数组元素仅剩一个时，达到递归边界，完成排序

划分数组

先任意选中数组一个值，然后将剩余的元素和这个值相比较，比这个值小的就交换到数组左侧，大的就交换到右侧（类似于冒泡排序的思想）

这个初始值一般情况下随机选取一个即可，但为了进一步减小快速排序退化为冒泡排序的概率，可以在左侧索引$\ l\ $ 和右侧索引$\ r\ $以及中间索引$\ (l+r)/2\ $指向的三个数中取中位数，来尽可能避免取到极端值

// 取三个数的中位数
int median(vector<int> &x, int l, int m, int r) {
    if ((x[l] < x[m]) ^ (x[l] < x[r])) {
        return l;
    } else if ((x[m] < x[l]) ^ (x[m] < x[r])) {
        return m;
    } else {
        return r;
    }
}
// 构建快速排序的两个分治数组，返回分割点的索引
int execute(vector<int> &x, int l, int r) {
    int m = l + r >> 1;
    int check = median(x, l, m, r);
    ...
}

为了方便处理更好地模拟冒泡排序，可以先将选中值挪到数组的首位，之后再处理$\ [l, r]\ $(因为在递归处理中除了选中值外的数组元素数量有可能不足$\ 2\ $，此时可能需要交换选中值和另一个值，所以要把$\ l\ $囊括进去)

int execute(vector<int> &x, int l, int r) {
    ...
    // 将选中的值暂时挪到数组最左边，方便对其余值的处理
    swap(x[check], x[l]);
    // 处理区间是第二个值到最后一个值
    int i = l, j = r;
    ...
}

之后

从右到左取第一个小于check的索引，

从左到右取第一个大于check的索引，

再将这两个值交换来让更小的值逐渐浮动到左侧

int execute(vector<int> &x, int l, int r) {    
    ...
    while (i < j) {
        // 从右到左找到第一个小于选中值的索引
        while (i < j && x[j] >= x[l]) {
            j --;
        }
        // 从左到右找到第一个大于选中值的索引
        while (i < j && x[i] <= x[l]) {
            i ++;
        }
        swap(x[i], x[j]);
    }
    ...
}

数据处理完了，但是别忘了初始的选中值还在第一位等待被插入

我们可以观察到，最终的i和j会返回一个终止循环的位置，这个位置也就是这两个子数组被分割的地方，但是该怎么在这个位置插入初始值呢？是插到后面还是前面呢？

分析一下代码的运行过程其实就有了答案：

∵ 循环中是先从右到左找小于选中值的索引

∴ 必然是满足条件的j先选出，再选出i的值

∴ 一旦发生i >= j必然是i在查找的过程中走到了j的位置

或j在查找的过程中走到了上一轮已经被j交换了的i的位置

∴ 最终返回的i必然是j上一轮找到的值的索引，必然小于选中值

∴ 可以通过交换x[l]和x[i]的方式把选中值放到分割点的位置

int execute(vector<int> &x, int l, int r) {
    ...
    // 把选中值再插入回数组中
    swap(x[l], x[i]);
    // 返回分割点的位置，也就是选中值被插入的位置
    return i;
}

到此，原数组就已经被成功分割为$\ [l, i)\ $和$\ (i, r]\ $两个子数组了

递归继续划分

因为这个划分已经满足了选中值左侧的任一元素都小于该值，右侧的任一元素都大于该值，所以直接递归处理左右两侧的子数组即可

void quickSort(vector<int> &x, int l, int r) {
    ...
    // 划分数组
    int split = execute(x, l, r);
    // 递归继续划分
    quickSort(n, l, split - 1);
    quickSort(n, split + 1, r);
}

空间复杂度优化

不难发现，如果按照以上方式处理子数组，当遇到一些特殊数据，例如完全倒序的数组时，递归深度会达到n - 1，$\ O(n)\ $的空间复杂度，那么有没有办法优化呢？

其实优化也很简单：每次都只处理较短的那个子数组，较长的子数组等到在下一个递归中被划分后再处理，这样就可以把最差空间复杂度优化到$\ O(log\ n)\ $

void quickSort(vector<int> &x, int l, int r) {
    while (l < r) { // 递归边界
        // 划分数组
        int split = execute(x, l, r);
        // 仅递归较短的子数组
        if (split - l < r - split) {
            quickSort(x, l, split - 1);
            // 较长的那个留到下次经划分后再处理
            // 故区间为 (split, r]
            l = split + 1;
        } else {
            // 同理
            quickSort(x, split + 1, r);
            r = split - 1;
        }
    }
}

排序完成

数组仅剩一个元素时代表已经排序完成，也就是递归边界

void quickSort(vector<int> &x, int l, int r) {
    // 数组仅剩一个元素
    if (l >= r) {
        return;
    }
    ...
}

完整代码

// 取三个数的中位数
int median(vector<int> &x, int l, int m, int r) {
    if ((x[l] < x[m]) ^ (x[l] < x[r])) {
        return l;
    } else if ((x[m] < x[l]) ^ (x[m] < x[r])) {
        return m;
    } else {
        return r;
    }
}
// 构建快速排序的两个分治数组，返回分割点的索引
int execute(vector<int> &x, int l, int r) {
    int m = l + r >> 1;
    int check = median(x, l, m, r);

    // 将选中的值暂时挪到数组最左边，方便对其余值的处理
    swap(x[check], x[l]);

    int i = l, j = r;
    /*
     * ∵ 循环中是先从右到左找小于选中值的索引
     * ∴ 必然是满足条件的 j 先选出，再选出 i 的值
     * ∴ 一旦发生 i >= j 必然是 i 在查找的过程中走到了 j 的位置
     *  或 j 在查找的过程中走到了上一轮已经被 j 交换了的 i 的位置
     * ∴ 最终返回的 i 必然是 j 上一轮找到的值的索引，必然小于选中值
     * ∴ 可以通过交换 x[l] 和 x[i] 的方式把选中值放到分割点的位置
     */
    while (i < j) {
        // 从右到左找到第一个小于选中值的索引
        while (i < j && x[j] >= x[l]) {
            j --;
        }
        // 从左到右找到第一个大于选中值的索引
        while (i < j && x[i] <= x[l]) {
            i ++;
        }
        swap(x[i], x[j]);
    }

    // 把选中值再插入回数组中
    swap(x[l], x[i]);

    return i;
}
void quickSort(vector<int> &x, int l, int r) {
    // 数组仅剩一个元素
    if (l >= r) {
        return;
    }
    // 划分数组
    int split = execute(x, l, r);
    // 递归继续划分
    quickSort(n, l, split - 1);
    quickSort(n, split + 1, r);
}