快速排序算法，即一种递归地讲数组按一定大小标准分成两组，小的一组在前，大的一组排在后的算法。
有关快速排序算法的文章和图解，网络上已经很多了，但阅读理解起来可能稍有困难，接下来我们将看到更容易理解的快速排序算法。
示例：以数组的首位作为基准（pivot），将小于ta的数置于ta的左边，大于ta的数在右边，左边只有1个元素，排序完成，而右边有4个数，那么把这4个数作为新的要排序的（抽象的）数组，重复上面的过程，最终基准所在的（抽象的）数组只有基准一个元素（如下图第二排的“2”），排序完成。
快速排序的复杂度
快排过程中需要移动元素的位置，很大程度上决定了时间复杂度。如果一个数组由大到小排列，而选取首位（最大数）为基准，则每一个元素都需要移动，而每一次移动的过程：对n个元素，考虑一般情况，分割一次数组（即小的排左边的过程）比较和交换元素的次数和n有关（虽然有的时候不用交换，但一定会比较）；而快排有一颗递归树，在数字比较随机，树比较均匀的情况下，树的高度近似logn，而树的每一层都有n个元素参与partition（数组分割成抽象数组后，多个抽象数组partition，因为partition的复杂度与n的一次方相关，在估测复杂度时，可以认为每一层都有n个元素参与一次partition），随机情况的复杂度即为n*logn。
最坏情况这棵树只沿着一颗子树延伸，树的高度为n，每一层仍有n个元素参与partition，复杂度为n*n。看一下数字从大到小排列的情况，例如100到1，首次partition会进行99次比较，最后一次partition进行1次比较，并且递归也会进行99次，从等差数列的公式也可以看出来它与n的平方相关。
复杂度的数学证明：
快速排序的代码（便于理解过程的版本，partition时移动数据，复杂度高）
#include <iostream>
using namespace std;
void QuickSort(int arr[],int start,int end){//递归的时候，start和end都相对于整个arr
if(start>=end){return;}
int temp=start;//保留start初始值
int pivot=arr[start];//以数组或分割后的抽象数组的第一个元素作为基准(pivot)
for(int i=start+1;i<=end;i++){//遍历arr[start]右边的元素
if(arr[i]<pivot){//当arr[i]比基准小
arr[start]=arr[i];//小的元素放到基准所在的位置
for(int j=i;j>start;j--){//遍历arr[start]到arr[i]，全体右移（arr[start]已经放了新的元素）
arr[j]=arr[j-1];//右移
}
arr[++start]=pivot;//由于start和i项交换，start+1项的值需要修正,完成交换后基准右移，所以start也要++
}
}//完成了一次左右分组（排序）
QuickSort(arr, temp, start-1);//对0号到start-1号元素排序，共有start个元素
QuickSort(arr, start+1, end);//对右边的元素排序
}
int main(int argc, const char * argv[]) {
int arr[]={3,4,2,7,5,8,6,1};//8个元素组成的的乱序数组
QuickSort(arr,0,7);//8个元素即0号到7号
for(int i=0;i<8;i++){
cout<<arr[i]<<endl;
}
return 0;
}
快速排序的代码（普通版本）
#include <iostream>
using namespace std;
int Partition(int arr[],int &start,int &end){
int pos=start;//(pos-start)用来记录小于等于arr[start]（基准）的数的个数，arr[start+1]到arr[pos]都小于基准
for(int i=start+1;i<=end;i++){//遍历基准以后的元素
if(arr[i]<arr[start]){//当某一项小于基准
if(arr[i]!=arr[++pos]){//如果任何一个大于基准的数后面所有元素中都没有小于x基准的数（即基准后的元素，前一部分全部小于基准，后一部分全部大于基准），则arr[i]==arr[pos]，不需要交换；否则需要交换
swap(arr[i], arr[pos]);
}
}
}
swap(arr[start], arr[pos]);//基准的位置开始没有移动，现在把基准的位置交换到小于基准的抽象数组的最右端，实现对数组的分割
return pos;
}
void QuickSort(int arr[],int start,int end){//递归的时候，start和end都相对于整个arr
if(start>=end){return;}//对应多种情况，pos可能等于start，pos-1为负，这种情况没有数小于基准，也不需要排序，对应start==end+1；pos等于start+1时，只有一个数比基准小，并且已经z位于基准左边，也不需要排序，对应start==end
int pos=Partition(arr, start, end);//对数组或抽象数组按基准排列，基准左边的数小于基准，右边大于基准
QuickSort(arr, start, pos-1);//对0号到start-1号元素排序，共有start个元素
QuickSort(arr, pos+1, end);//对右边的元素排序
}
int main(int argc, const char * argv[]) {
int arr[]={3,4,2,7,5,8,6,1};//8个元素组成的的乱序数组
QuickSort(arr,0,7);//8个元素即0号到7号
for(int i=0;i<8;i++){
cout<<arr[i]<<endl;
}
return 0;
}
两个指针的快速排序&&Partition的优化
待补充
参考资料：
1.《算法导论》第7章：快速排序
我的博客即将同步至腾讯云+社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=1q1xzkj9mydbq