#笔记-基础算法
快速排序
将序列按从小到大或从大到小顺序排序。
时间复杂度 \(O(nlogn)\)，不稳定。
步骤
-
确定分界点 \(x\)：\(q[l]\)、\(q[(l + r) \div 2]\)，\(q[r]\)、\(q[(l +r+1)\div 2]\)。
注意，上面分界点用列举的前两项时，递归处理
qsort(l, j); qsort(j + 1, r)；反之递归处理qsort(l, i); qsort(i + 1, r)。否则会有边界问题（举序列中只有两个数的情况思考）。 -
调整区间：两个指针 \(i,j\) 往中心移动，左边遇到 \(\ge x\) 的数时停下，右边遇到 \(\le x\) 的数停下，再交换。
为什么不是“左边遇到 \(> x\) 的数时停下，右边遇到 \(< x\) 的数停下”呢？
－注意序列中所有数相同的情况。 -
递归求解左右两段。
不难得出，当 \(i \ge j\) 时，\(i\) 左边都为 \(\le x\) 的数，\(j\) 右边都为 \(\ge x\) 的数，故分两段递归即可。具体细节见上文。
代码如下：
void qsort(int l, int r) {
if(l >= r) return;
int x = a[(l + r) / 2], i = l - 1, j = r + 1;
while(i < j) {
do i++; while(a[i] < x);
do j--; while(a[j] > x);
if(i < j) swap (a[i], a[j]);
}
qsort(l, j); qsort(j + 1, r);
}
例题
思路1：将原数组 \(a\) 排序后输出 \(a[k]\) 即可。排序可 sort()，也可手写。时间复杂度 \(O(nlogn)\)。
思路2：看向快排模板。
快排分段递归时，我们拿到了数组分界点的指针。因此，我们只需要在两段中选择 \(k\) 在内的一段进行递归排序即可。
时间复杂度计算 \(O(n + \frac{n}{2} + \frac{n}{4} + \dots) < O(2n) = O(n)\)。
void qsort(int l, int r) {
if(l >= r) return;
int x = a[(l + r) / 2], i = l - 1, j = r + 1;
while(i < j) {
do i++; while(a[i] < x);
do j--; while(a[j] > x);
if(i < j) swap (a[i], a[j]);
}
if(k <= j) qsort(l, j); else qsort(j + 1, r);
}