题目描述

给定你一个长度为n的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。

输入格式
输入共两行，第一行包含整数 n。
第二行包含 n个整数（所有整数均在 1∼109范围内），表示整个数列。

输出格式
输出共一行，包含 n个整数，表示排好序的数列。

数据范围
1≤n≤100000

输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5

算法1

//#include[HTML_REMOVED]

using namespace std;

const int N=1e6+10;

int n;
int q[N];

void quick_sort(int q[],int l,int k){
if(l>=k) return;

int x=q[k+l>>1],i=l-1,j=k+1;
//x能再取边界l是因为，题目的数据加强，取边界时间复杂度会变成o(n^2)超时
//注：边界k不可取，取了会变成死循环


while(i<j){
    do{i++;}while(x>q[i]);
    do{j--;}while(x<q[j]);
    if(i<j) swap(q[i],q[j]);
}
quick_sort(q,l,j);
quick_sort(q,j-1,k);

}

int main(){
scanf(“%d”,&n);//注：scanf比cin快几十倍
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;

}

算法2

//#include[HTML_REMOVED]

using namespace std;

const int N=1e6+10;

int n;
int q[N];

void quick_sort(int q[],int l,int k){
if(l>=k) return;

int x=q[l + k + 1 >> 1],i=l-1,j=k+1;
//注意l+k+1，+1是为了向上取整，保证不取到l边界，死循环。
//另外边界的时间复杂度也不再满足题目的加强数据时间复杂度要求

while(i<j){
    do{i++;}while(x>q[i]);
    do{j--;}while(x<q[j]);
    if(i<j) swap(q[i],q[j]);
}
quick_sort(q,l,i-1);
quick_sort(q,i,k);

}

int main(){
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;

}