快速排序

一、定义

1.1 基本思想

快速排序（Quick Sort）的基本思想是，从待排序数组中随机选取一个“基数”，进行切分（partition）：

• 将小于基数的数据放在左边，大于“基数”的数据放到右边，这样“基数”就归位了。
• 然后，对“基数”左右两边的数组以相同的方式分别进行递归排序。

1.2 关键点

切分（partition）
切分的方式有很多种，无论采用什么方式切分，切分的结果就是将数组分成3部分：基数、小于等于基数部分、大于等于基数部分。

切分的抽象API

/**
* 将序列a[lo..hi]进行切分，切分后a[lo..j-1] <= a[j] <= a[j+1..hi]
* 
* @return 返回切分后基数a[j]所在的索引j
*/
int partition(Comparable[] a, int lo, int hi)

1-1 切分示意图

二、实现

2.1 示例

以对序列“6、1、2、7、9、3、4、5、10、8”的一趟“基数归位”的快排为例，快速排序的具体步骤如下：

1. 选择最左边的数“6”作为基数，哨兵j先开始移动（j--），直到找到一个小于6的数停下。接下来，哨兵i开始移动（i++），直到找到一个大于6的数停下。最后哨兵i停在数字5面前，哨兵j停在数字7面前
   

为什么必须哨兵j先开始动？
因为哨兵i左侧的数肯定都小于基数，哨兵j右侧的数肯定都大于基数。如果先移动哨兵i，那么当i遇到j时，i所处的位置肯定大于基数，此时如果将该位置的数与“基数”交换，会导致比基数大的数反而放到了基数左侧。

2. 交换哨兵i和哨兵j所在的位置的数，结果如下：

   
   

3.继续重复上述步骤，过程如下，直到哨兵i和哨兵j相遇，然后将所处位置的数字与基数交换：

---

以“6，1，2，7，9，3，4，5，10，8”为例的完整快速排序流程：

三、源码

public class QuickSort {
    public static void sort(Comparable[] a) {
        StdRandom.shuffle(a);   //打乱数组
        sort(a, 0, a.length - 1);
    }
 
    // quicksort the subarray from a[lo] to a[hi]
    private static void sort(Comparable[] a, int left, int right) {
        if (left >= right)
            return;
        int j = partition(a, left, right);
        sort(a, left, j - 1);
        sort(a, j + 1, right);
    }
 
    private static int partition(Comparable[] array, int left, int right) {
        Comparable cardinal = array[left]; // 设置基数
 
        int i = left, j = right;
        while (i != j) {
            // 哨兵j先动,找到第一个比基数小的数
            while (i < j && array[j] >= cardinal) {
                j--;
            }
 
            // 哨兵i动,找到第一个比基数大的数
            while (i < j && array[i] <= cardinal) {
                i++;
            }
 
            // 交换i和j所在的数
            swap(array,i,j);
        }
        return j;
    }
}

四、性能分析

4.1 复杂度分析

• 时间复杂度
  O(NlgN)

4.2 算法改进

1. 切换到插入排序
   由于插入排序对于小数组十分高效，可以在排序小的子数组时用插入排序，而不是继续递归。
2. 大量重复元素的数组优化
   当待排序数组中有大量重复元素（如人员生日资料、性别等）时，快速排序的递归性会使元素全部重复的子数组经常出现，这有很大改进潜力（比如采用三向切分），通过改进可以将线性对数级别的性能提高到线性级别。

五、三向切分的快速排序

5.1 基本思想

普通快速排序的效率依赖于切分数组的效果，如果每次切分都发生在数组的中间，即每次都能将数组对半分，这是最好情况。
但是，对于含有大量重复键的序列，如果初始时不做随机化处理，快排的效果很差，比如当键全部相同或初始有序时，每次切分只会有一个元素被交换，剩下的数组还是一个大数组。

5.2 实现

三向切分的快速排序，维护3个指针，如下：
lt：使得a[lo...lt-1]中元素都小于v
gt：使得a[gt+1...hi]中元素都大于v
i：使得a[lt...i-1]中元素都等于v

具体步骤：

1. 初始时：i=low
2. i向右遍历过程中，执行如下操作：
   如果a[i]<v，将a[i]和a[lt]交换，lt和i都加1；
   如果a[i]>v，将a[i]和a[gt]交换，gt减1；
   如果a[i]=v，将i加1；
3. 直到i>gt时，循环结束。
   5-2 三向切分示意图

源码：

// quicksort the subarray a[lo .. hi] using 3-way partitioning
private static void sort(Comparable[] a, int lo, int hi) {
    if (lo >= hi)
        return;
    int lt = lo, gt = hi, i = lo;
    Comparable v = a[lo]; // 选取切分基数
    while (i <= gt) {
        int cmp = a[i].compareTo(v);
        if (cmp < 0)
            exch(a, lt++, i++);
        else if (cmp > 0)
            exch(a, i, gt--);
        else
            i++;
    }
    // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
    sort(a, lo, lt - 1);
    sort(a, gt + 1, hi);
}

5.3 性能分析

三向切分的快速排序算法将排序时间从线性对数级降低到线性级别。
其时间复杂度介于O(N)和O(NlgN)之间，这依赖于输入数组中重复元素的数量。