题目描述
给定你一个长度为n的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行,第一行包含整数 n。
第二行包含 n 个整数(所有整数均在1~109范围内),表示整个数列。
输出格式
输出共一行,包含 n 个整数,表示排好序的数列。
数据范围
1≤n≤100000
样例
输入样例:
5
3 1 2 4 5
输出样例:
1 2 3 4 5
分析
使用快排方法:
1.选取:一个比较值
2.整理:数列中小于这个数放在这个数的左侧,将数列中大于这个数放在这个数的右侧
3.进行这个数的左右两子部分进行快排操作。
C++代码
#include <iostream>
using namespace std;
const int N = 1e5; //这个是输入数据的限制值
int n;
int q[N]; // 将大量数组开辟在全局(内存中的static区域),防止栈过爆
void quick_sort(int q[], int L, int R){
if(L >= R) return; //1.边界条件判断
// 2.选取一个比较值
int x = q[(L + R)>>1];
int i = L - 1; //这里的i,j要选取 L - 1和R + 1是因为在下面的while()比较的顺序,使i,j游标落在比较的
int j = R + 1; //数字上
while(i < j){
while(q[++i] < x); // 找到左侧的第一个大于比较值的游标位置
while(q[--j] > x); // 找到右侧的第一个小于比较值的游标位置
if(i < j) swap(q[i] , q[j]); // 如果两个i,j游标还未相遇,那么就交换
}
quick_sort(q, L, j); //快排左侧
quick_sort(q, j + 1, R); //快拍右侧
}
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;
}
2.整理:数列中小于这个数放在这个数的左侧,将数列中大于这个数放在这个数的右侧
对于这种 5 4 3 4 2 4 2
比较数为4,这样 在中间的4和4,是不是就交换后还相等。就成为小于等于和大于等于了。