[模板题]快速排序

来源：模板题

算法标签：分治，快速排序

题目描述：785. 快速排序

给定你一个长度为n的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在1~109范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

1≤n≤100000

输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

题目思路

1.设立中间值为标记值
2.左右两个指针往中间走，
2.1.如果左边指针走到了的值大于标记值，停止
2.2.如果右边指针走到了的值小于标记值，停止
3.交换两个值
4.知道指针重合或者越界停止
5.确保此时左半部分小于标记值，右半部分大于标记值
6.分治递归

题目代码

#include<iostream>
#include<cstring>

using namespace std;
const int N=1E5+10;

void swap(int &a,int &b){a^=b^=a^=b;}//交换

void quick_sort(int a[],int l,int r)//快排 a数组 l左指针 r右指针
{
    if(l==r)return;//退出
    
    int i=l-1,j=r+1,x=a[l+r>>1];//因为下面是dowhile所以i,j是两边的值，a[l+r>>1]取中间值为标记值
    
    while(i<j)//ij未重合
    {
        do i++;while(a[i]<x);//找到左半部分大于标记值的值
        do j--;while(a[j]>x);//找到右半部分小于标记值的值
        if(i<j)swap(a[i],a[j]);//交换
    }
    
    quick_sort(a,l,j),quick_sort(a,j+1,r);//分治递归
}

int main()
{
    int n;
    cin>>n;
    
    int a[N];
    memset(a,0,sizeof a);
    for(int i=0;i<n;i++)cin>>a[i];
    
    quick_sort(a,0,n-1);
     
    for(int i=0;i<n;i++)cout<<a[i]<<" ";
    
    return 0;
}``