题目描述

给定你一个长度为$n(1\le n\le100000)$的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

样例

输入：

5
3 1 2 4 5

输出：

1 2 3 4 5

算法1

(快速排序) $\Theta(n\log n)$

快速排序的基本思想:通过一趟排序将数组分成两个部分,其中一个部分都比关键字小,另一个部分都比关键字大,然后再分别对这两部分进行这种操作,最后就可以达到全部有序.通常我们取待排序部分的第一个值为关键字.

我们能不能把步骤想的更具体一点,怎么样做才能把数分成这样的两个部分?

上面的图片解释了一趟快速排序的原理,如果你有足够的想想象力,可以把红色,蓝色下标想象成两个机器人,它们不停的移动去判断值,一但符合条件,就把箱子里的值仍给另一个机器人,自己停止,另一个机器人又开始工作,这样的不停往返的下去,就可以把数分成两个部分了。

C++ 代码

#include<cstdio>
using namespace std;
int a[300000];
int n;
void kp(int x,int y){
    if(x>=y) return;
    int jz=a[x];
    int i=x,j=y;
    while(i!=j){
        while(a[j]>=jz&&i<j) j--; 
        while(a[i]<=jz&&i<j) i++; 
        swap(a[i],a[j]);
    } 
    a[x]=a[j];
    a[j]=jz;
    kp(x,j-1);
    kp(j+1,y);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    kp(1,n);
    for(int i=1;i<=n;i++) printf("%d ",a[i]);
    return 0;
}