QuickSort快速排序

QuickSort快速排序思想如下，每次选一个数出来当做基准数，通过移动数组使得这个数字左边都小于基准数，右边都大于基准数，然后不断递归划分直到每个区间为都为1即完成排序。
主要步骤如下
1、每次从数组中选一个基数a[r]（这里采取最后一个数为基准数）
2、从前往后遍历到r，记得当前数字是否比基数a[r]小，小的话就与比基准数大的一个数交换。
3、将a[i+1]与a[r]交换即可。
4、将区间low~i 与 i+2~high重复步骤1，直到区间为1

一次划分演示如下：

1.png 2.png

代码

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100010;

int partition(int *a,int l,int r){
    int value = a[r];
    int i = l-1;
    for(int j = l;j<r;j++){
        if(a[j]<=value){
            i++;
            swap(a[i],a[j]);
        }
    }
    swap(a[i+1],a[r]);
    return i+1;
}

void quicksort(int *a,int l,int r){
    if(l<r){
        int mid = partition(a,l,r);
        quicksort(a,l,mid-1);
        quicksort(a,mid+1,r);
    }
}

int a[MAXN];

int main(){
    int n;
    scanf("%d",&n);
    for(int i = 0;i<n;i++)
        scanf("%d",&a[i]);
    //sort(a,a+n);
    quicksort(a,0,n-1);
    for(int i = 0;i<n;i++)
        printf("%d ",a[i]);
    return 0;
}