题目描述
给定你一个长度为n的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行,第一行包含整数 n。
第二行包含 n 个整数(所有整数均在1~109范围内),表示整个数列。
输出格式
输出共一行,包含 n 个整数,表示排好序的数列。
数据范围
1≤n≤100000
样例
输入样例:
5
3 1 2 4 5
输出样例:
1 2 3 4 5
C++ 代码
快速排序(O(n*logn))
思想:
快排属于分治算法,分治算法都有三步:
1. 分成子问题
2. 递归处理子问题
3. 子问题合并
快速排序的思路:
- 先找一个基数,可以随便选择数组里面的一个数,建议取中间那个。
- 然后用两个变量分别指向数组的左右两边,不断对基数的左右两边进行遍历。
遍历的过程中,我们保持这样一个条件:左边的数永远小于等于基数,右边的数永远大于等于基数。 - 当这两个变量遍历时,左边的数大于基数或者右边的数小于基数,那么我们退出循环。
如果此时这两个变量还没有走出各自的范围,那就交换这两处的值。 - 最后我们不断对数组的左边和右边进行同样的处理,也就是递归。最后形成有序。
#include <iostream>
using namespace std;
//定义范围,防止越界
const int N = 1e5 + 10;
//n个数
int n ;
//n个数放进数组
int q[N];
//l:左边界 r : 右边界
void quickSort(int q[] , int l ,int r){
//递归终止情况
if(l >= r) return ;
/*
第一步,分成子问题,先随意取一个数组里面的值,一般取中间值
i , j 分别是两个指针,i从前往后,j从后往前
初始化的时候,定义在边界的外边
*/
int x = q[(l + r) >> 1] , i = l-1, j = r + 1;
//注意是i < j ,不是l < r。这是因为先排一遍,把所有小于等于x的值都放到左边,右边就是大于等于x的值。
while(i < j){
//当这个while跳出的时候,此时q[i] > x
do i++; while(q[i] < x);
//但这个while跳出的时候,此时q[j] < x
do j--; while(q[j] > x);
//但是i < j仍然成立,那么交换这两个指针位置的值。
if(i < j) swap(q[i],q[j]);
}//i > j 跳出,进行下一次的递归处理左右两边的情况
//第二步:递归处理子问题。也就是对于一个数组分成左右边界时,分别对左右进行排序。
quickSort(q,l,j);
quickSort(q,j + 1 , r);
//第三步:子问题合并.快排这一步不需要操作,但归并排序的核心在这一步骤
}
int main(){
//当输入数据量比较大的时候,采用scanf会比cin时间快一些。
scanf("%d",&n);
for(int i = 0 ; i < n ; i++)scanf("%d",&q[i]);
quickSort(q,0,n - 1);
for(int i = 0 ; i < n ; i++)printf("%d ", q[i]);
return 0;
}