排序问题，是生活中非常常见的问题，关于排序问题，足以专门开辟一个专栏来写，包括最简单的选择排序啦、冒泡法啦、桶排法啦等等。排序方法有很多种，不同的排序方法有各自不同的特点。在这里介绍一种排序——快速排序。它的时间复杂度是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、按照从大到小的顺序，用快排的方式来实现。
