快排是一种最常用的排序算法，因为其平均的时间复杂度是nlgn，并且其中的常数因子比较小。
一.快速排序 快排和合并排序一样都是基于分治的排序算法;快排的分治如下: 分解:对区间A[p,r]进行分解,返回q,使得A[p–q-1]都不大于A[q]A[q+1,r]都大于A[q]; 求解:对上面得到的区间继续递归进行快排 合并:因为快排是原地排序,所以不需要特别的合并 从上可以看出最重要的就是分解函数,其按关键值将数组划分成3部分，其具体实现的过程见代码注释。
我们一般取数组的最后一个元素作为划分比较的关键值，如下面的代码
int Paratition(int *a,int p,int r){ 划分的过程其实就是将每一个元素通过比较放到这两个区间去(主要是i的增长)。 i=p-1;for(int j=p;j<r;j++)if(a[j]<=key){i++;swq(a[j],a[i]);}swq(a[i+1],a[r]);return i+1;}
但是我们也可以在区间a[p,r]中任取一个元素作为关键值，这样可以使得每次的划分更加的均匀，从而提高效率，对应的代码如下：
///随机划分函数int RandParatition(int *a,int p,int r){int x=rand()%(r-p+1)+p; ///产生一个[p,r]之间的随机数xswq(a[x],a[r]); ///将a[x],a[r]交换,使得将a[x]作为划分的关键值return Paratition(a,p,r);}
下面给出一份快排的完整代码：
namespace std;void swq(int &a,int &b){int t=a;a=b;b=t;}///划分函数int Paratition(int *a,int p,int r){int key=a[r];int i=p-1;for(int j=p;j<r;j++)if(a[j]<=key){i++;swq(a[j],a[i]);}swq(a[i+1],a[r]);return i+1;}///快排void QiuckSort(int *a,int p,int r){if(p>=r)return;int q=Paratition(a,p,r);QiuckSort(a,p,q-1);QiuckSort(a,q+1,r);}而是每次随机的在a[p,r]中取一个元素作为划分的关键值。///随机划分函数int RandParatition(int *a,int p,int r){int x=rand()%(r-p+1)+p; ///产生一个[p,r]之间的随机数xswq(a[x],a[r]); ///将a[x],a[r]交换,使得将a[x]作为划分的关键值return Paratition(a,p,r);}///随机快排函数void RandQiuckSort(int *a,int p,int r){if(p>=r)return;int q=RandParatition(a,p,r); ///随机快排调用的是随机划分函数RandParatition(a,p,q-1);RandParatition(a,q+1,r);}int main(){int n=5,a[10];cout<<“请输入”<<n<<“个数：”<<endl;for(int i=1;i<=n;i++)cin>>a[i];///RandQiuckSort(a,1,n);QiuckSort(a,1,n);cout<<“排序以后的数组：”<<endl;for(int i=1;i<=n;i++)cout<<a[i]<<” “;cout<<endl; return 0;}
二.快排的时间复杂度：快排的时间复杂度分析是一件很麻烦的事情，我们知道如果每次的划分都是完全不平衡的即T(n)=T(n-1)+O(n)，那么快排的时间复杂度是n^2；如果每次都是均等的划分即T(n)=T(n/2)+T(n/2)+O(n)，那么时间复杂度就是nlgn。但是这两种划分在平时都是不常见的，所以不具有代表性；但是如果我们考察一些不平衡的划分，如每次都是9:1即T(n)=T(n/10)+T(n*9/10)+O(n)，我们可以发现在这种情况下时间复杂度仍然是nlgn；并且即使不平衡性进一步增加(只要不是完全不平衡)，达到99:1的程度，时间复杂度仍然会是nlgn(关于这一段算法导论上有大篇幅的证明)。所以我们可以说快排的平均时间复杂度是nlgn，这个复杂度是经常可以达到的。
三.常用排序算法的时间复杂度总结 以下简单的罗列出前面学习过的排序算法的时间复杂度，不给出严格的证明。
排序算法最好时间复杂度最坏时间复杂度 插入排序O(n)(原数组有序)O(n^2)(原数组逆序) 合并排序O(nlgn)O(nlgn) 堆排序O(nlgn)O(nlgn) 快速排序O(n^2)(每次都是完全不平衡划分) O(nlgn)（大多数情况）
从上面的表格看似乎合并排序和堆排序都要比快排好，但实际中因为快排O(nlgn)的时间复杂度是经常可以达到，，并且快排中的常数因子比较小，所以在实际中快排一般是最快的排序算法，不愧他”快排”的称号。
每一发奋努力的背后，必有加倍的赏赐。
