做题做到 QuickSelect，结果感觉已经有点记不清 QS 了……在此用力复习一下 QS。

本文解答所有关于 QS 的疑难杂症。

首先上代码，来自 Sedgewick 的 Algorithm：

public class Quick
{
    public static void sort(Comparable[] a)
    {
        StdRandom.shuffle(a);          // Eliminate dependence on input.
        sort(a, 0, a.length - 1);
    }

    private static void sort(Comparable[] a, int lo, int hi)
    {
        if (hi <= lo) return;
        int j = partition(a, lo, hi);    // Partition (see page 291).
        sort(a, lo, j - 1);              // Sort left part a[lo .. j-1].
        sort(a, j + 1, hi);              // Sort right part a[j+1 .. hi].
    }

    private static int partition(Comparable[] a, int lo, int hi)
    {  // Partition into a[lo..i-1], a[i], a[i+1..hi].
        int i = lo, j = hi + 1;          // left and right scan indices
        Comparable v = a[lo];            // partitioning item
        while (true)
        {  // Scan right, scan left, check for scan complete, and exchange.
            while (less(a[++i], v)) if (i == hi) break;
            while (less(v, a[--j])) if (j == lo) break;
            if (i >= j) break;
            exch(a, i, j);
        }
        exch(a, lo, j);    // Put v = a[j] into position
        return j;          // with a[lo..j-1] <= a[j] <= a[j+1..hi].
    }
}

1. QuickSort 的总体思路：

在要排序的序列中选定一个 pivot（这里选最左边的元素），将序列进行 partition，使得所有位于pivot 左边的元素都小于 pivot，位于右边的元素都大于 pivot，但此时左右两部分被视为无序状态：

[……（无序的左边部分）……]，[（pivot）]，[……（无序的右边部分）……]

这样还不足以排序, 但我们发现，只要分别 sort 一下左边和右边部分，整个序列就有序了：

function sort(a[])
{
  partition(a[]);
  sort(a[]左边部分);
  sort(a[]右边部分)；
}

到此QuickSort 已经结束了，EOF

——“然鹅，sort 左边部分和右边部分不还是要 sort 吗？我们还是没有实现 sort 啊！”

不过可能你已经发现了，上面那个 function sort(a[]) 是一个递归函数！也就是说，每次我们分成左右两个子序列，都要进行 parttition，直到这个子序列只有一个元素！这样仅靠 partition，我们就完成了排序，sort()函数作为递归体，不断调用 partition()来处理子序列。

2. partition()

到此，我们已经知道 partition 要达到什么目的，只需要再实现 partition 的功能：首先先要选取一个 pivot，关于 pivot 的选取至关重要，因为会极大地影响复杂度，稍后详细分析时间复杂度。

public class QuickSort
{
    public static int partition(int[] a, int low, int high)
    {
        int pivot = int[low];
        int i = low, j = high + 1;
        while(true)
        {
            while(a[++ i] < pivot)  // pointer i keeps going if pointed element is less than pivot
            {
                if(i >= high)   break;
            }
            while(a[-- j] > pivot)  // pointer j keeps going if pointed element is larger than pivot
            {
                if(j <= low)    break;
            }
            if(i >= j)  // if two pointer cross
                break;
            swap(a, i , j);
        }
        swap(a, low, j);    // put pivot between two partitions
        return j;           // return the index of pivot
    }

    public static void sort(int[] a, int low, int high)
    {
        int pivotIndex = partition(a, low, high);
        sort(a, low, pivot - 1);
        sort(a, pivot + 1, high);
    }
}

*为什么与 pivot 比较的时候是“<”、">"？为什么还要交换两个相同的元素？
理想状态下我们希望每次切分都得到两个规模相同的子序列，也就是说 i，j 两个指针能停下来的时候就停下来，从而使最后 Pivot 的位置保持一个比较靠中间的位置。否则，pivot 最终的 index 过于偏向一边，就会增大递归的深度（best case是logN，而 worst case 则是 N）。

3. 3-way-partition

如果元素大量重复，上述办法则还有可以提高的空间，因为我们交换了大量重复的元素，还可以压榨这部分的复杂度：

Sedgewick 配图相当好，注意 lt 、gt 和 i 三个指针的位置（相当精确）；灰色部分是当前还没扫描到的部分

对于每次切分：从数组的左边到右边遍历一次，维护三个指针，其中lt指针使得元素（arr[0]-arr[lt-1]）的值均小于切分元素；gt指针使得元素（arr[gt+1]-arr[N-1]）的值均大于切分元素；i指针使得元素（arr[lt]-arr[i-1]）的值均等于切分元素，（arr[i]-arr[gt]）的元素还没被扫描，切分算法执行到i>gt为止。每次切分之后，位于gt指针和lt指针之间的元素的位置都已经被排定，不需要再去处理了。之后将（lo,lt-1）,（gt+1,hi）分别作为处理左子数组和右子数组的递归函数的参数传入，递归结束，整个算法也就结束。

public class Quick3way
{
     private static void sort(Comparable[] a, int lo, int hi)
     {  
        if (hi <= lo) return;
        int lt = lo, i = lo+1, gt = hi;
        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++;
        }  // Now a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
        sort(a, lo, lt - 1);
        sort(a, gt + 1, hi);
     }
}

这里就没有一个单独的 partition()，而是将其整合进了 sort() 里面。

4. pivot 的选取

pivot 的选取至关重要，理想状态是每次都取到位于中间的 pivot，这样就能保证递归深度为 LogN。如果对一个一定程度上有序的序列使用这种快排，复杂度则是 O（n）。

改进：虽然我们每次都取最左边的当 pivot，但只要在取之前对 array 进行 shuffle，将有序性去除，就能很好的避免掉进 O（N）递归深度的坑里。

至于 shuffle 的方式有好几种，比如 kunth-shuffle 等等，another story。我们也可以直接用 API。

5. 复杂度分析

（鸽）