快速排序和归并排序
快速排序
算法流程：
- 确定分界点
x：q[l], q[r], q[(l + r) / 2], q[rand()] - 调整区间：使得左边区间里的所有数都
<= x，右边区间里的所有数都>= x，注意分界点 x 不一定在分界处 - 递归处理左右两段
由于左边区间一定满足小于等于右边区间，那么一定不会存在逆序对（因为递归出口一定是一个单独的数，而这就表示逆序对一定会在某次调整区间操作后变为顺序）。而 一个没有逆序对的数列一定是有序数列（这是很显然的，若一个数列不是有序数列，那么一定存在一对数对，它们的大小和序号大小方向相反，这正是逆序对）。
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n;
int q[N];
void quick_sort(int q[], int l, int r) {
if (l >= r) {
return ;
}
int x = q[(l + r) / 2], i = l - 1, j = r + 1;
while (i < j) {
do { i ++; } while (q[i] < x);
do { j --; } while (q[j] > x);
if (i < j) {
swap(q[i], q[j]);
}
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 0; i < n; i ++) {
cin >> q[i];
}
quick_sort(q, 0, n - 1);
for (int i = 0; i < n; i ++) {
cout << q[i] << " ";
}
return 0;
}首先介绍算法：
- 相向双指针
i和j分别从左右端点出发 - 每次判断
q[i], q[j]和分界点x的大小关系- 如果
q[i] < x，i继续右移，否则停下 - 如果
q[j] > x，j继续左移，否则停下
- 如果
- 如果满足
i < j，则找到了一对 逆序对，将二者交换
一个直译的算法：
void quick_sort(int q[], int l, int r) {
if (l >= r) {
return ;
}
int x = q[l], i = l, j = r;
while (i < j) {
while (q[i] < x) i ++;
while (q[j] > x) j --;
if (i < j) {
swap(q[i], q[j]);
}
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}形参 l, r 分别是左右端点下标。该算法无法通过以下测试案例：
2
1 1显然，无法通过的原因是此时的 i 由于 q[l] == q[i] 将无法实现 i ++，同样的 j 也存在这种情况。不过最最重要的一点是：当 swap 了二者之后，我们的算法逻辑中是认为找到了一对逆序对（其实也有可能二者相同）逆序对交换后是一定满足左小右大的，因此我们不需要判断交换后的逆序对和分界点的大小关系，然而这里面由于算法逻辑的问题，依然进行了判断，这样碰到相同的数构成的 逆序对 就陷入了死循环。
为了解决交换后无需判断这个问题，可以在交换后加一个 flag 指示器：
void quick_sort(int q[], int l, int r) {
if (l >= r) {
return ;
}
int x = q[l], i = l, j = r;
bool flag = false;
while (i < j) {
if (flag) {
i ++;
j --;
flag = false;
}
while (q[i] < x) i ++;
while (q[j] > x) j --;
if (i < j) {
swap(q[i], q[j]);
flag = true;
}
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}这时有人要问：为什么一定要加 flag 而不是直接在 swap 的下一行加上 i ++, j --; 呢？这是因为这样做提前将 while (q[i] < x) i ++; 这件事放到了上一个循环中，而这样会导致 while (i < j) 判断出现问题：
3
2 3 1以这个为例，如果按照想当然的写法，i, j 交换后分别右移左移，两者同时指向 3，但此时尚未对 3 和分界点 x 的大小关系做判断，而是直接退出了 while 大循环进入分治阶段，这导致了问题的出现。应该先进入大循环，根据是否 swap 直接对 i, j 进行右移左移，然后再判断新的 i, j 对应的数与分界点 x 之间的大小关系，得到正确的分治部分。
我们注意到，这个结构中 while (i < j) 和 if (i < j) 的判断条件是一样的，也就是说：只要 if 条件成立进行 swap 后，一定可以进入下一次 while 循环，这就表示 i, j 一定会先右移左移（也就是说，每一次进入 while 循环后 i, j 一定会先右移左移）。那么我们只需要让开始的 i, j 分别在出发点左侧和右侧，实现第一步与循环内容自洽即可。
void quick_sort(int q[], int l, int r) {
if (l >= r) {
return ;
}
int x = q[(l + r) / 2], i = l - 1, j = r + 1;
while (i < j) {
do { i ++; } while (q[i] < x);
do { j --; } while (q[j] > x);
if (i < j) {
swap(q[i], q[j]);
}
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}看似没有道理的 进循环先右移左移，其实包含了这样一种原理。
边界问题
第二个值得思考的问题是边界问题，也就是分治后的两部分该用什么端点？
我们首先要知道，这样的 do while 结构得到的 i 一定是从左到右第一个满足 q[i] >= x 的，j 一定是从右到左第一个满足 q[j] <= x 的。
i, j 终止情况无非两种：
i = j，此时q[i] = q[j] = x，因此有两种选择：[l, j], [j + 1, r]（或[l, i], [i + 1, r]）[l, j - 1], [j, r]（或[l, i - 1], [i, r]）
i = j + 1，此时q[j] < x < q[i]，因此只有一种选择：[l, j], [j + 1, r]- 或者写成
[l, i - 1], [i, r]
综上考虑，只有两种选择：
[l, j], [j + 1, r][l, i - 1], [i, r]
问题又来了，是不是 [l, j] 和 [l, i - 1] 就没有区别了呢？
答案显然是否定的，考虑这样一种情况：
2
1 2当我们取分界点 x = q[l] = 1 时，此时 i, j 都会移动到 1 所在的位置，即 i = j = 0，对应 i = j 这种情况，此时 [l, j] 和 [l, i - 1] 分别为 [0, 0] 和 [0, -1]，显然 [l, i - 1], [i, r] 对应的分治结果 [0, -1], [0, 1] 不符合要求，导致死循环。
同样的，如果分界点采用 x = q[r] = 2，那么 i, j 都会移动到 2 所在的位置，也就是 i = j = 1，此时 [l, j], [j + 1, r] 对应的分治结果 [0, 1], [2, 1] 不符合要求，需要采用 [l, i - 1], [i, r]。
如果采用中间点也是一样的：
q[(l + r) / 2]可能会取到左端点，因此要用[l, j], [j + 1, r]q[(l + r + 1) / 2]可能会取到右端点，因此要用[l, i - 1], [i, r]
最后提一嘴：有些样例会卡 q[l], q[r]，建议写中间点，不容易被卡。
快速排序的朴素做法
TODO: 快速排序的朴素做法
快速排序的期望时间复杂度
TODO：快速排序的时间复杂度推导
第 k 个数
快速选择算法：找到第
- 设分界点左侧元素个数为
sl = j - l + 1 - 如果
k <= sl，则进入左侧递归 - 如果
k > sl，则进入右侧递归，同时找的是第k - sl小的数 - 由于每次只进入一侧，因此时间复杂度大大降低
归并排序
归并排序的主要思想也是分治。
算法思想：
- 确定分界点
mid = (l + r) / 2 - 递归排序左右两半部分，认为此时已经排好序了（递归基只有一个数自然是有序的）
- 二路归并，将两个有序数组归并为一个大的有序数组
依然是双指针算法。
算法流程：
i, j分别指向两个有序数组当前尚未归并的最小值- 比较二者的大小，其中较小的进入结果数组
res，同时将其指针右移一位 - 直到某一个数组为空，将另一个数组直接放到结果数组后面即可
如果两个数相同，一般把第一个数放到结果数组中，这样得到的算法是 稳定的。
逆序对的数量
- 和归并排序一样，都是假设左右部分都确定了逆序对数量
merge_sort(l, mid)和merge_sort(mid + 1, r)- 需要对两个有序数列求合并后的逆序对