快速排序

基本思想

1.先从数列中找到一个数作为基准数

2.分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边

3.再对左右区间重复第二步，直到各区间只有一个数

//little->big
void quickSort(int left,int right,int arr[])
{
    if(left>=right) return;//函数出口
    int i,j,base,temp;
    i=left,j=right;
    base=arr[left];//取最左边的数作为基准数
    while(i<j)
    {
        while(arr[j]>=base&&i<j) j--;
        while(arr[i]<=base&&i<j) i++;
        if(i<j)
        {
            temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
        }
    }
    //基准数归位
    arr[left]=arr[i];
    arr[i]=base;
    quickSort(left,i-1,arr);//递归左边
    quickSort(i+1,right,arr);//递归右边
}

//完整代码
#include<iostream>
using namespace std;
int n,a[1000001];
void qsort(int l,int r)//应用二分思想
{
    int mid=a[(l+r)/2];//中间数
    int i=l,j=r;
    do{
        while(a[i]<mid) i++;//查找左半部分比中间数大的数
        while(a[j]>mid) j--;//查找右半部分比中间数小的数
        if(i<=j)//如果有一组不满足排序条件（左小右大）的数
        {
            swap(a[i],a[j]);//交换
            i++;
            j--;
        }
    }while(i<=j);//这里注意要有=
    if(l<j) qsort(l,j);//递归搜索左半部分
    if(i<r) qsort(i,r);//递归搜索右半部分
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    qsort(1,n);
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";
}