快速排序
作者:
WQIAN
,
2023-04-06 20:52:51
,
所有人可见
,
阅读 190
/*
*基础算法一:快速排序
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100000;
int q[N];//待排序数组
void quick_sort(int q[N],int l,int r){//快速排序
if(l>=r)return;//l>=r直接退出
int i=l-1,j=r+1,x=q[l+r>>1];//初始定义i,j,x是数组的中间值
while(i<j){
//移动i和j指针,只要i和j还没重合(i<j)就继续循环
do i++;while(q[i]<x);//将i指针向后移一位(i指针是从l的前一位开始的)
//循环的条件:q[i]<x,将小于x的数放在前半部分
//遇到大于等于x的数,i暂停移动
do j--;while(q[j]>x);//将j指针向前移一位(j指针是从r的后一位开始的)
//循环的条件:q[i]>x,将大于x的数放在后半部分
//遇到小于等于x的数,j暂停移动
if(i<j)swap(q[i],q[j]);//此时i指向大于等于x的数,j指向小于等于x的数,交换i,j指向的数
} //一次循环结束,当i<j时继续循环,直到i,j相遇
quick_sort(q,l,j);//递推,继续排l到j(i,j相遇的位置)
quick_sort(q,j+1,r);//递推,继续排j+1(i,j相遇的后一个位置)到r
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>q[i];//读入
}
quick_sort(q,0,n-1);
for(int i=0;i<n;i++){
cout<<q[i]<<' ';//输出
}
return 0;
}