题目描述
给定你一个长度为 n的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行,第一行包含整数 n。
第二行包含 n个整数(所有整数均在 1∼10的九次方范围内),表示整个数列。
输出格式
输出共一行,包含 n个整数,表示排好序的数列。
数据范围
1≤n≤100000
样例
输入样例:
5
3 1 2 4 5
输出样例:
1 2 3 4 5
C++ 代码
#include<iostream>
#define N 100000
using namespace std;
int a[N];
void quick_sort(int a[],int l,int r)
{
if(l>=r) return; //先判断,如果数组长度为0或1,那不用排序
int x=a[l + r >> 1],i=l,j=r; //第一步:确立分界点,我是以数组中间的点作为分界点
//l+r>>1 表示l+r的和的二进制数向右移一位,对于非负整数,右移一位等价于除以2(即(l+r)/2)
//第二步,调整区间 目的是保证分界点x左边所有的数都 ≤x ,分界点右边的数都 ≥x,但此时分界点左右两段是无序的
while(i<=j)
{
while(a[i]<x)i++;
while(a[j]>x)j--;
if(i<=j) swap(a[i++],a[j--]);
}
//第三步,进行递归处理左右两段 ,目的是调整两段子数组的顺序
//每次递归调用都会选择一个新的基准,并对基准的左右两个子数组进行进一步的分区和排序,直到整个数组变得有序。
quick_sort(a,l,j);
quick_sort(a,i,r);
}
int main()
{
int n;
scanf("%d",&n); //数据量比较大的时候,用scanf会快,无论如何,scanf速度是不会慢于cin的
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
quick_sort(a,0,n-1);
for(int i=0;i<n;i++)
printf("%d ",a[i]);
return 0;
}