基本思想

通过一轮的排序将序列分割成独立的两部分，其中一部分序列的关键字（这里主要用值来表示）均比另一部分关键字小。继续对长度较短的序列进行同样的分割，最后到达整体有序。在排序过程中，由于已经分开的两部分的元素不需要进行比较，故减少了比较次数，降低了排序时间。

一次划分基本步骤

1. 一个基准值（通常是第一个数），两个指针（前指针i，后指针j），起始时前指针指向第一个数，后指针指向最后一个数。
2. 后指针从后往前扫描，遇到比基准值小的数a[j]，a[i]与a[j]交换，前指针i+1（为下一步从前往后扫描做准备）
3. 前指针从前往后扫描，遇到比基准值大的数a[i]，a[j]与a[i]交换，后指针j+1（为下一步从后往前扫描做准备）
4. 重复步骤二，直到 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;
    }

时间复杂度

1. 最好情况：O(nlogn)
2. 最坏情况：每次划分只比上一次少了一个元素，也就是每次划分都只拿到了最大或最小的元素，退化为冒泡排序，n*n
3. 一般情况：O(nlogn)

证明：快速排序时间复杂度为O（n×log（n））的证明

算法改进

• 基准值的选择方面。
  1、选取随机数作为枢轴。
  但是随机数的生成本身是一种代价，根本减少不了算法其余部分的平均运行时间。
  2、 使用左端，右端和中心的中值做为枢轴元。
  经验得知，选取左端，右端，中心元素的中值会减少了快排大约 14%的比较。
  3、每次选取数据集中的中位数做枢轴。
  选取中位数的可以在 O(n)时间内完成。（证明见《算法导论（第二版） 》） P111 第九章中位数
• 快速排序在处理小规模数据时的表现不好。
  这个时候可以改用插入排序。
  当数据规模小于一定程度时，改用插入排序。具体小到何种规模时，采用插入排序，这个理论上还不解，一些文章中说是 5 到 25 之间。SGI STL 中的快速排序采用的值是 10。