AcWing 785. 快速排序
原题链接
简单
作者:
种花家的老六
,
2022-09-25 22:03:50
,
所有人可见
,
阅读 297
快速排序正解
首先我们都知道快速排序可以用系统函数解。
于是就产生了如下的代码:
#include <iostream>
#include <algorithm>//注意sort在algorithm头文件里
using namespace std;
const int N = 100010;//定义数组长度
int n;
int a[N];
int main(){
cin >> n;//输入,当然scanf也没毛病
for (int i = 0; i < n; i ++ ) cin >> a[i];//循环输入,当然从1开始也没毛病
sort(a, a + n);//调用系统函数sort
for (int i = 0; i < n; i ++ ) cout << a[i] << ' ';//循环输出,当然printf也没毛病
return 0;
}
这种方法虽然好,但是无法通过面试,于是,我们就要手写sort函数
怎么写呢???
我们就可以用 分治 的思想:
1.确定分界点:q[l] q[(l + r) / 2] q[r] 随机
2.调整范围:我们需要找到一个分界点x,使得它左边的数都小于等于它,右边的数都大于等于它
3.递归处理左右两段:
(1).遍历q[l~r],如果q[i] <= x,就将x插到左边去,如果q[i] >= x,就将x插到右边去
(2).还原
于是,我们就产生了这样的代码:
#include <iostream>
using namespace std;
const int N = 100010;
int q[N];
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + 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()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
quick_sort(q, 0, n - 1);
for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
return 0;
}
正解,一行就够:
sort(a,a+n);
或sort(a+1,a+1+n);