采用算法导论上的实现方式，用java实现。

快排算法核心的部分便是partition过程，这里的partition采取最后一个元素作为pivot，i和j两个指针都从头向后扫描，如下图所示，数组被分为4个部分。

 

算法执行的过程：

 

代码实现：包括快速排序， 寻找第K大元素， 洗牌算法。

 

import java.util.Arrays;import java.util.Random;public class MySort {    /**     * 快速排序     *      * @param a     */    public static void quickSort(int[] a) {        qSort(a, 0, a.length - 1);    }    private static void qSort(int[] a, int p, int r) {        if (p < r) {
   // 递归算法不要忘记了出口            int q = partition(a, p, r);            qSort(a, p, q - 1);            qSort(a, q + 1, r);        }    }    private static int partition(int[] a, int p, int r) {        int x = a[r];        int i = p - 1;        int j = p;        for (j = p; j < r; j++) {            if (a[j] <= x) {                i++;                swap(a, i, j);            }        }        swap(a, i + 1, r);        return i + 1;    }    private static void swap(int[] a, int i, int j) {        if (i != j) {            int tmp = a[i];            a[i] = a[j];            a[j] = tmp;        }    }    /**     * 返回第k大的元素。     *      * @param a     * @param k     * @return     */    public static int selectKSmallest(int[] a, int k) {        if (k >= a.length || k < 0)            return -1;        qSelect(a, k, 0, a.length - 1);        return a[k];    }    private static void qSelect(int[] a, int k, int p, int r) {        if (p < r) {            int q = partition(a, p, r);            if (q > k)                qSelect(a, k, p, q - 1);            else if (q < k)                qSelect(a, k, q + 1, r);            else                return;        }    }    /**     * 洗牌算法     *      * @param a     */    public static void shuffle(int[] a) {        for (int i = 0; i < a.length; i++) {            int k = new Random().nextInt(i + 1);// return a random value in                                                // [0,i].            int tmp = a[k];            a[k] = a[i];            a[i] = tmp;        }    }    public static void main(String[] args) {        int[] a = { 2, 8, 7, 1, 3, 5, 6, 4 };        System.out.println("before sorting:" + Arrays.toString(a));        quickSort(a);        System.out.println("after sortint:" + Arrays.toString(a));        shuffle(a);        System.out.println("after shuffling:" + Arrays.toString(a));        System.out.println(selectKSmallest(a, 3));    }}

 

 

正确性证明：

 

 

双指针向内的快速排序：   Algorithms里讲的很好，看

import java.util.Arrays;public class test {    public static void quickSort2(int[] a) {        qSort(a, 0, a.length - 1);    }    /**     * 注意1：递归终止条件 l>=r      * 注意2：i和j初始位置，用do while保证至少有一次变化，不会原地不动     * 注意3：j最终的位置是要和l交换的位置。     * 注意4：对于跟pivot相等的情况，应该停住两个指针并交换，虽然交换次数增多，但是保证partition更平均，复杂度更低。     */    private static void qSort(int[] a, int l, int r) {        if (l >= r)            return;        int t = a[l];        int i = l, j = r + 1;        while (true) {            do {                i++;            } while (i <= r && a[i] < t);            do {                j--;            } while (a[j] > t);            if (i > j)                break;            swap(a, i, j);        }        swap(a, l, j);        qSort(a, l, j - 1);        qSort(a, j + 1, r);    }    private static void swap(int[] a, int i, int j) {        int tmp = a[i];        a[i] = a[j];        a[j] = tmp;    }    public static void main(String[] args) {        int[] a = { 1, 1, 1, 1, 1 };        System.out.println(Arrays.toString(a));        quickSort2(a);        System.out.println(Arrays.toString(a));    }}

 

 

快速排序细节及优化：

1. pivot随机化：不一定每次都选第一个为pivot， 可以先做 swap（a[0], a[rand(l,r)]）；或者选取三个样本中的中位数作为pivot

2. 两个指针移动的时候对于跟pivot相等的元素，应该停住交换，而不是跨过。（虽然增加了交换时间，但是保证了极端情况，比如元素全部相等情况下，partition分区极不均匀的情况。）

3. r-l 小于一定的cutoff之后，选用insertion sort等方法。

4. 3-way-partation。：当数组有大量重复元素时，这种优化复杂度甚至可以降到线性。