本文共 1985 字，大约阅读时间需要 6 分钟。

快速排序（Quick Sort）由 C. A. Hoare 在1962年提出，是冒泡排序的一种改进。采用了分治策略，将原问题划分成若干个规模更小但与原问题相似的子问题，然后递归方法解决，合并问题的解。

基本思想

通过一趟排序将序列分割成独立的两个部分，其中一部分的所有记录的关键值都比另外一部分的所有关键值小，按照这种方法对两部分记录分别进行快速排序，递归进行。

一趟快速排序的主要步骤

1. 设置两个变量i、j，初值分别为low,high,分别表示待排序序列的起始下标和终止下标
2. 将第i个记录暂存在变量pivot中，即pivot = r[i]
3. 从下标为j的位置开始由后向前一次搜索，当找到第1个比pivot的关键值小的记录是，将该记录向前移动到下标为i的位置，i = i + 1
4. 从下标为i的位置开始右前向后一次搜索，当找到第1个比pivot的关键字值大的记录是，将该记录向后移动到下标为j的位置上，j = j - 1
5. 重复步骤3、4，直到 i == j 为止
6. 最后，令r[i] = pivot

性能分析

空间复杂度：快速排序在系统内部需要栈结构实现递归，每层递归调用时的指针和参数均需要用栈存放。其递归过程可用一颗二叉树表示。如果每次划分较为均匀，则递归树的高度为$O(logn)$，则栈空间为$O(logn)$。最坏情况下，递归树是一颗单支树，树的高度为$O(n)$，则空间复杂度为$O(n)$。

时间复杂度：最好的情况$O(nlogn)$，最坏的情况是初始关键字序列有序或基本有序时，在快速排序过程中每次划分只能得到一个子序列，退化为冒泡排序，时间复杂度为$O(n^2)$。就平均性能来说，快速排序使基于关键字比较的内部排序算法中速度最快的，平均时间复杂度为$O(nlogn)$。

java代码实现：

/**     * 快速排序     O(nlog2n)     * 递归实现     * @param arr 需要排序的表     * @param low 起始位置     * @param high 结束位置     */    public static 
   
    > void quickSort(T[] arr,            int low, int high) {        if (low < high) {            // 分割递归调用快速排序            int pivotPos = partition(arr, low, high);            quickSort(arr, low, pivotPos - 1);            quickSort(arr, pivotPos + 1, high);        }    }    /**     * 快速排序分割     * @param arr 原始表     * @param i 起始位置     * @param j 结束位置     * @return     */    public static 
    
     > int partition(T[] arr,            int i, int j) {        T pivot = arr[i];   // 第i个元素作为支点        // 从表的两端交替向中间扫描        while (i < j) {            while (i < j && pivot.compareTo(arr[j]) <= 0) {                j--;            }            if (i < j) {                arr[i] = arr[j];    // 将比支点记录小的记录向前移动                i++;            }            while (i < j && pivot.compareTo(arr[i]) >= 0) {                i++;            }            if (i < j) {                arr[j] = arr[i];    // 将比支点记录大的向后移动                j--;            }        }        arr[i] = pivot;     // 记录支点位置并返回        return i;    }
    
   

参考：