[//]: # 快排(推荐题解模板,请替换blablabla等内容 ^^)
题目描述
给定你一个长度为 n
的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
基础内容——快速排序
快速排序不那么难,中心思想是这样的:
首先由一个数组,x将数组分为两半,作为一个分界线,小于x在x左侧,大于x在x右侧。
然后设定一个i,一个j,i的初始值为左边界-1,j的初始值为右边界+1,+1和-1算是提前量,下一个循环才会真正接触边界。i和j逐渐会向x靠近,如果不符合条件,就用swap函数交换
这样循环一遍后,用j将数组分为两半,进而排序。
对了,我是个蒟蒻,如果理解有误,欢迎dalao们指出错误,我会读每条评论滴~
C++ 代码
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int q[N];
void quick_sort (int q[], int l, int r){
if(l >= r) return;//确认有1个以上的数据
int x = q[l+r>>1], i = l-1, j = r+1;
while(i < j){
do i++; while(q[i] < x);
do j--; while(q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j);
quick_sort(q, j+1, r);
}
int main(){
scanf("%d", &n);
for (int i ; i < n ; i ++ ) scanf("%d", &q[i]);
quick_sort(q, 0, n-1);
for (int i ; i < n ; i ++ ) printf("%d ", q[i]);
return 0;
}