快速排序

快速排序

// 链接：https://www.acwing.com/problem/content/787/
#include <bits/stdc++.h>
using namespace std;
/*
快速排序的思想是根据分治处理的
每次将他分解成两个区域，知道区域的长度为1
然后将两个有序区域进行合并
*/
const int N = 1e6+7;
int s[N];
int n;
void qks(int l,int r)
{	
	if(l >= r) return;
    //越界返回
    int i = l - 1, j = r + 1, x = s[l + r >> 1];
    while(i < j)
    {
        do i++; while(s[i] < x);
        do j--; while(s[j] > x);
        if(i < j) swap(s[i], s[j]);
    }
	qks(l,j);
	qks(j+1,r);
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&s[i]);
	
	qks(1,n);
	
	for(int i=1;i<=n;i++)printf("%d ",s[i]);
	
	return 0;	
}
//c++调用快排 qsort