基础算法复习:快速排序
题目描述
给定你一个长度为n的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行,第一行包含整数 n。
第二行包含 n 个整数(所有整数均在1~109范围内),表示整个数列。
输出格式
输出共一行,包含 n 个整数,表示排好序的数列。
数据范围
1≤n≤100000
样例
输入样例:
5
3 1 2 4 5
输出样例:
1 2 3 4 5
算法
快速排序
快速排序算法基于分治的思想,以某个点为分界划分区间然后分而治之。整个排序主要可以分为三个阶段:确定分界点,调整区间,递归处理,其中第二个阶段调整区间是重点。下面分别简要说明三个阶段。
第一阶段:确定分界点,选择q[L],q[L+R/2],q[R]是常用的,当然也可以是其他一点。以下以选择中点为例。
第二阶段:调整区间,使得分界点左边的数都小于等于分界点,右边的数都大于等于分界点,这也是快排算法中的核心一步。有一种暴力的做法是开辟两个数组a,b,遍历q[],如果q[i]<=x(分界点)就放到a数组,否则放到b数组,最后再填回去q数组,不过这样比较浪费空间。更加简洁优美的做法是用两个指针i,j分别先指向数组的头和尾,每次都由i先出发,若q[i] < x就一直前进,否则停下来,然后是j出发,若q[j]>x就一直往开头走,否则停下。两者都停下时,i所指的数是大于等于x的,j所指的数是小于等于x的,若i,j还未相遇,则交换q[i],q[j],如此循环,直到i,j相遇或者穿过。由于每次q[j]>x时j才会继续前进,而碰到q[j]<=x时又会与>=x的q[i]交换,因此最后j左边的都是<=x的数,j右边都是>=x的数。
第三阶段:递归处理。分别处理左边和右边。
时间复杂度
递归的终点是区间长度为1,而每次递归平均区间长度是原区间长的1/2,因此递归一共有logn层,每次要处理的区间总长度都为n,因此平均时间复杂度为O(nlogn);
参考文献
acwing 算法基础课 快排模板
C++ 代码
#include <cstdio>
#include <algorithm>
using namespace std;
void quick_sort(int q[],int l,int r);
int q[100010];
int main(){
int n;
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;
}
void quick_sort(int q[],int l,int r){
if(l>=r) return ;
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);
}