基本思想
通过一轮的排序将序列分割成独立的两部分，其中一部分序列的关键字（这里主要用值来表示）均比另一部分关键字小。继续对长度较短的序列进行同样的分割，最后到达整体有序。在排序过程中，由于已经分开的两部分的元素不需要进行比较，故减少了比较次数，降低了排序时间。
一次划分基本步骤
- 一个基准值（通常是第一个数），两个指针（前指针i，后指针j），起始时前指针指向第一个数，后指针指向最后一个数。
- 后指针从后往前扫描，遇到比基准值小的数a[j]，a[i]与a[j]交换，前指针i+1（为下一步从前往后扫描做准备）
- 前指针从前往后扫描，遇到比基准值大的数a[i]，a[j]与a[i]交换，后指针j+1（为下一步从后往前扫描做准备）
- 重复步骤二，直到 i == j，则 a[i] = a[j] = 基准值，且基准值左边的数都比基准值小，基准值右边的数都比基准值大
算法实现
public int[] sort(int[] a, int left, int right){
if (left < right){//递归出口，left=right说明一组只有一个元素
int i = left;
int j = right;
int temp = a[left];
while (i < j){//一次划分，i=j说明指针相遇，指针所指元素左边均比a[i]小，右边均比a[i]大
while (i < j && a[j] >= temp) {j--;}//后指针向前扫描找到比基准值小的元素
if(i < j) { a[i++] = a[j];}//若i < j则说明找到，交换
while (i < j && a[i] <= temp) {i++;}
if(i < j) { a[j--] = a[i];}
}
a[i] = temp;
sort(a, left, i - 1);
sort(a, i + 1, right);
}
return a;
}
时间复杂度
- 最好情况：O(nlogn)
- 最坏情况：每次划分只比上一次少了一个元素，也就是每次划分都只拿到了最大或最小的元素，退化为冒泡排序，n*n
- 一般情况：O(nlogn)
算法改进
- 基准值的选择方面。
1、选取随机数作为枢轴。
但是随机数的生成本身是一种代价，根本减少不了算法其余部分的平均运行时间。
2、 使用左端，右端和中心的中值做为枢轴元。
经验得知，选取左端，右端，中心元素的中值会减少了快排大约 14%的比较。
3、每次选取数据集中的中位数做枢轴。
选取中位数的可以在 O(n)时间内完成。（证明见《算法导论（第二版） 》） P111 第九章中位数 - 快速排序在处理小规模数据时的表现不好。
这个时候可以改用插入排序。
当数据规模小于一定程度时，改用插入排序。具体小到何种规模时，采用插入排序，这个理论上还不解，一些文章中说是 5 到 25 之间。SGI STL 中的快速排序采用的值是 10。
