|
|
|
|
|
## [$AcWing$ $785$. 快速排序](https://www.acwing.com/problem/content/787/)
|
|
|
|
|
|
|
|
|
|
|
|
### 一、题目描述
|
|
|
|
|
|
给定你一个长度为 $n$ 的整数数列。
|
|
|
|
|
|
|
|
|
|
|
|
请你使用快速排序对这个数列按照从小到大进行排序。
|
|
|
|
|
|
|
|
|
|
|
|
并将排好序的数列按顺序输出。
|
|
|
|
|
|
|
|
|
|
|
|
**输入格式**
|
|
|
|
|
|
输入共两行，第一行包含整数 $n$。
|
|
|
|
|
|
|
|
|
|
|
|
第二行包含 $n$ 个整数（所有整数均在 $1∼109$ 范围内），表示整个数列。
|
|
|
|
|
|
|
|
|
|
|
|
**输出格式**
|
|
|
|
|
|
输出共一行，包含 $n$ 个整数，表示排好序的数列。
|
|
|
|
|
|
|
|
|
|
|
|
**数据范围**
|
|
|
|
|
|
$1≤n≤100000$
|
|
|
|
|
|
|
|
|
|
|
|
**输入样例：**
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
5
|
|
|
|
|
|
3 1 2 4 5
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
**输出样例：**
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
1 2 3 4 5
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
### 二、算法原理
|
|
|
|
|
|
|
|
|
|
|
|
* 每次排序时选取一个基准，将小于基准的数全部放到基准点的左边，将大于或等于基准的数全部放到基准的右边。
|
|
|
|
|
|
|
|
|
|
|
|
* 完成后，得到了两个 **整体** 上有序的子数组，再递归继续，直至所有元素完成排序。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
#### 算法模拟
|
|
|
|
|
|
假设对$6, 1, 2, 7, 9, 3, 4, 5,10, 8$这$10$个数进行排序：
|
|
|
|
|
|
|
|
|
|
|
|
**本次模拟的基准是以数组的第一个元素为基准的。**
|
|
|
|
|
|
|
|
|
|
|
|
从后向前扫描,$i$去向右找第一个大于 **基准$6$** (**这个$6$是选择的第一元素，代码中我们将选择中间位置的元素，道理都是一样的**) 的数字,$j$向左查找第一个小于基准$6$数字：
|
|
|
|
|
|
<center><img src='https://images2017.cnblogs.com/blog/1230454/201801/1230454-20180124094950569-1570587181.png'></center>
|
|
|
|
|
|
|
|
|
|
|
|
找到$7$和$5$,交换$7$和$5$
|
|
|
|
|
|
<center><img src='https://images2017.cnblogs.com/blog/1230454/201801/1230454-20180124095142850-1884986244.png'></center>
|
|
|
|
|
|
|
|
|
|
|
|
继续前进,找到$9$和$4$,然后交换
|
|
|
|
|
|
<center><img src='https://images2017.cnblogs.com/blog/1230454/201801/1230454-20180124095407725-16725917.png'></center>
|
|
|
|
|
|
|
|
|
|
|
|
$i>=j$，交换$6$和$3$
|
|
|
|
|
|
<center><img src='https://images2017.cnblogs.com/blog/1230454/201801/1230454-20180124095611490-180314539.png'></center>
|
|
|
|
|
|
|
|
|
|
|
|
交换之后：$3, 1, 2, 5, 4, 6, 9, 7, 10, 8$, 一趟排序结束。
|
|
|
|
|
|
|
|
|
|
|
|
以基准值$6$划分的两堆数据,左手边都比$6$小，右手边都比$6$大，$6$在中间，然后再用同样的办法递归处理左右两边即可，此时，$6$就不参与了。
|
|
|
|
|
|
|
|
|
|
|
|
### 三、实现代码
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 100010;
|
|
|
|
|
|
int q[N];
|
|
|
|
|
|
int n;
|
|
|
|
|
|
|
|
|
|
|
|
/**
|
|
|
|
|
|
* 功能：利用快速排序对数组进行排序
|
|
|
|
|
|
* @param q 要排序的数组
|
|
|
|
|
|
* @param l 左端下标位置
|
|
|
|
|
|
* @param r 右端下标位置
|
|
|
|
|
|
*/
|
|
|
|
|
|
void quick_sort(int q[], int l, int r) {
|
|
|
|
|
|
if (l >= r) return;
|
|
|
|
|
|
int i = l - 1, j = r + 1; // 从界外开始
|
|
|
|
|
|
int x = q[(l + r) >> 1]; // 基准值为中间位置的数值
|
|
|
|
|
|
|
|
|
|
|
|
while (i < j) { // 没有碰面就一直按这个逻辑跑一跑
|
|
|
|
|
|
do i++;
|
|
|
|
|
|
while (q[i] < x); // i哨兵向右走，找到第一个大于基准值的数，这个数的位置需要调整
|
|
|
|
|
|
|
|
|
|
|
|
do j--;
|
|
|
|
|
|
while (q[j] > x); // j哨兵向左走，找到第一个小于基准值的数，这个数的位置需要调整
|
|
|
|
|
|
|
|
|
|
|
|
if (i < j) swap(q[i], q[j]); // 如果还没有碰面，就对调一下
|
|
|
|
|
|
}
|
|
|
|
|
|
// 当退出上面的循环，就是两个人碰面的时候，此时左右两半都已经是有序的了，再递归处理
|
|
|
|
|
|
quick_sort(q, l, j), quick_sort(q, j + 1, r);
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
int main() {
|
|
|
|
|
|
cin >> n;
|
|
|
|
|
|
for (int i = 1; i <= n; i++) cin >> q[i];
|
|
|
|
|
|
quick_sort(q, 1, n);
|
|
|
|
|
|
for (int i = 1; i <= n; i++) printf("%d ", q[i]);
|
|
|
|
|
|
return 0;
|
|
|
|
|
|
}
|
|
|
|
|
|
```
|
|
|
|
|
|
### 四、快速排序算法的证明与边界分析 【了解】
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
<font color='red' size=4><b>琢磨太深，使人痛苦！</b></font>
|
|
|
|
|
|
|
|
|
|
|
|
**[参考文档](https://www.acwing.com/solution/content/16777/)**
|
|
|
|
|
|
|
|
|
|
|
|
**顺带一提用$i$做划分时的模板**
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
void quick_sort(int q[], int l, int r) {
|
|
|
|
|
|
if (l >= r) return;
|
|
|
|
|
|
int i = l - 1, j = r + 1;
|
|
|
|
|
|
int x = q[(l + r + 1) >> 1]; // 非得要用i这里要修改！
|
|
|
|
|
|
|
|
|
|
|
|
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, i - 1), quick_sort(q, i, r); // 非得要用i这里要修改！
|
|
|
|
|
|
}
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
|
