题目描述

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

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

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

输入格式

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

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

输出格式

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

数据范围

$1≤n≤100000$

输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

主要思想

分治

思路

1.确定分界点：

①$q[l]$ ②$q[(l+r)/2]$ ③$q[r]$ ④随机

2.调整区间：

（不一定以$x$为分界点，两个区间不一定相等）

※使得第一个区间里的数都小于等于$x$，第二个区间里的数都大于等于$x$

$i$从左边向中间走，$j$从右边向中间走，直到$i$找到大于等于$x$的数，$j$找到小于等于$x$的数，$i$和$j$进行交换（$swap$），直到相遇（或交叉）为止，从相遇（交叉）的位置一分为二

证明：

任何时刻，$i$左边的所有的数都小于等于$x$。因为如果一个小于等于$x$，$i$会走到下一个数，而交换过来的也一定小于等于$x$，同理，$j$右边的数也都大于等于$x$

3.递归处理两个区间：

原理：因为左边的最大值小于等于右边的最小值，所以当左右两边排好序的时候，整个序列就排好序了

边界问题：
如果在函数里$i=l$，那么$x!=q[l]$，否则会死循环
例：
输入

2
1 2

若$x=q[l]$，函数中的循环执行完了以后，$i=0$，那第一层递归就会跳出，提二层递归为$quick_sort(q,0,2)$，之后就会死循环，可以取$q[(l+r)/2]$（这种边界问题建议直接把模板背过）

同理，当递归取$j$时，$x$不能取$q[r]$

代码

#include<iostream>
using namespace std;
const int N=1e6+10;
int q[N];
void quick_sort(int q[],int l,int r)
{
    if(l>=r)
        return;
    int x=q[(l+r)/2];
    int i=l-1;//如果这里用i=l;下面就要改成while循环
    int j=r+1;
    while(i<j)
    {
        do i++; while(q[i]<x);//用do-while一定会先++，所以上面定义的时候i=l-1;
        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()
{
    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;
}

备用思路(快排想不起来的时候可以顶一下)

1.先开两个数组

2.将q数组里小于等于x的数放进a数组里，将q数组里大于x的数放进b数组里

3.再将a，b数组里的数放进q数组