叠甲x
只是个曾经学过算法的蒟蒻深夜睡不着在试图整理以前学过的知识，或许已经忘了又或许没忘……
总之，虽然所有代码均经过了测试，但仍然不敢保证完全准确，如果哪里有误欢迎大佬指正（
快速排序
快速排序 (Quick Sort)，是一种高效且复杂度相对稳定的排序算法，在一定优化之后更可以达到绝大多数情况下 O(n log n) 的时间复杂度和不超 O(log n) 的空间复杂度
原理
快速排序的实现基于分治思想：
每次将原数组分割为两个子数组，保证左子数组中任一元素都小于右子数组中任一元素，然后递归处理两个子数组直到数组只剩一个元素，从而完成对整个数组的排序
具体实现
-
划分数组为两个子数组
-
递归继续划分两个子数组
-
子数组元素仅剩一个时，达到递归边界，完成排序
1. 划分数组
先任意选中数组一个值，然后将剩余的元素和这个值相比较，比这个值小的就交换到数组左侧，大的就交换到右侧（类似于冒泡排序的思想）
这个初始值一般情况下随机选取一个即可，但为了进一步减小快速排序退化为冒泡排序的概率，可以在左侧索引 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);
...
}
为了方便处理（更好地模拟冒泡排序x），可以先将选中值挪到数组的首位，之后再处理 [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] 两个子数组了
2. 递归继续划分
因为这个划分已经满足了选中值左侧的任一元素都小于该值，右侧的任一元素都大于该值，所以直接递归处理左右两侧的子数组即可
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);
}
2.1 空间复杂度优化
不难发现，如果按照以上方式处理子数组，当遇到一些特殊数据，例如完全倒序的数组时，递归深度会达到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;
}
}
}
3. 排序完成
数组仅剩一个元素时代表已经排序完成，也就是递归边界
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;
}
// 最差空间复杂度 O(n)
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);
}
// 最差空间复杂度 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;
}
}
}
论坛对Markdown的适配并不是很好，想要更好的阅读体验可以下载附件里的.md文件（以及可直接编译运行的快速排序模版源码）
