排序问题，是生活中非常常见的问题，关于排序问题，足以专门开辟一个专栏来写，包括最简单的选择排序啦、冒泡法啦、桶排法啦等等。排序方法有很多种，不同的排序方法有各自不同的特点。在这里介绍一种排序——快速排序。它的时间复杂度是nlogn，几乎是所有排序方法中最快的一种了。

一、快排的思想

快排基本思路是（以从小到大排序）：（1）选择一个“基准”；（2）将比“基准”小的数放在左边，比“基准”大的数放在右边；（3）继续递归调用该函数，直到排序中只剩下1个数。
其中在第（2）步中，为了节省时间，往往是在左边找到“大的数”（大于基准），右边找到“小的数”（小于基准），然后交换两者的数值。直到左右两边相遇，即完成了关于“基准”的一次排序（即实现比基准小的数放左边，比基准大的数放右边）。
值得注意的是，在选择“基准”上，有多种不同的方式，比较常见的选择方式是：选第一个数和选中间的数这两种。下面将分别用这两种方式来实现。

二、快排的代码实现

1、选中间值为“基准”

#include <iostream>
using namespace std;
const int maxn=10000;
int a[maxn+10]; //定义全局变量

void qsort(int left, int right){//两个参数是数组的左下标和右下标 
    int i=left, j=right;
    int key=a[(i+j)/2]; //基准，中间值 
    while(i<=j){
        while(a[i]<key )//不能越过基准，所以不能有等号 
            i++;
        while(a[j]>key)
            j--;
        if(i<=j){
            int t=a[i];
            a[i]=a[j];
            a[j]=t;
            i++;
            j--;
        }
    }
    if(i<right) //递归调用右边 
        qsort(i,right);
    if(left<j)  //递归调用左边 
        qsort(left,j);
}

int main(){
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>a[i];
    qsort(1,n); //快排函数，调用数组，从a[1]到a[n]进行排序
    for(int i=1; i<=n; i++) //输出快排后的数 
        cout<<a[i]<<" ";  
    return 0;   
}

2、选第一个数为“基准”

#include <iostream>
using namespace std;
const int maxn=10000;
int a[maxn+10]; //定义全局变量

void qsort(int left, int right){//两个参数是数组的左下标和右下标 
    if(left>right) //至少要有1个数以上才需要排序。即right-left+1>=1,化简为right>=left，反过来，结束排序的条件为它的非命题。 
        return ;
    int i=left, j=right;
    int key=a[left];//选第一个数为基准
    while(i<j){
        while(a[j]>=key && i<j)
            j--;
        while(a[i]<=key && i<j)
            i++;
        if(i<j){
            int t=a[i];
            a[i]=a[j];
            a[j]=t;
        }
    }
    a[left]=a[i];
    a[i]=key;
    qsort(i+1,right); //右边
    qsort(left,i-1);  //左边 
}

int main(){
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>a[i];
    qsort(1,n); //快排函数，调用数组，从a[1]到a[n]进行排序
    for(int i=1; i<=n; i++) //输出快排后的数 
        cout<<a[i]<<" ";  
    return 0;   
}

三、快排练习

1、思考：选择第一个数为“基准”时，为何要从右边开始出发？
2、按照从大到小的顺序，用快排的方式来实现。