快速排序 (Quick Sort)

通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

基本思想

1, 从数列中挑出一个元素，称为 “基准”（pivot）。
2, 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3, 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

示例(Java)

    public static <E extends Comparable<E>> void  sort(E[] arr) {
        Random rnd = new Random();
        sort(arr, 0, arr.length-1, rnd);
    }

    private  static <E extends Comparable<E>> void sort(E[] arr, int l, int r, Random rnd) {
        if (l >= r) return;
        int p = partition(arr, l, r, rnd);
        sort(arr, l, p, rnd);
        sort(arr, p+1, r, rnd);
    }

    //以arr[l]为基准，将<它的值放在它左边，>=等于它的值放在它右边
    private static <E extends Comparable<E>> int partition(E[] arr, int l, int r, Random rnd) {
        //生成[l, r]之间的随机索引
        //优化1 解决如果数组是完全有序数组效率降低的问题，随机选择一个标准值
        int p = l + rnd.nextInt( r - l + 1);
        swap(arr, l , p);

        // arr [l+1...j] < v, arr[j+1...i] >= v
        int j = l;
        for (int i = l +1; i<= r; i++){
            if (arr[i].compareTo(arr[l]) < 0) {
                j ++;
                swap(arr, i, j);
            }
        }
        swap(arr, l , j);
        return j;
    }

    private static <E> void swap(E[] arr, int l, int j) {
        E t = arr[l];
        arr[l] = arr[j];
        arr[j] = t;
    }

思路

逻辑

partition.1

partition.2

partition.3

双路快速排序法：

进一步优化解决，假如数组中有大量相同数据，效率降低的问题

示例(Java)

    //双路快速排序
    //以arr[l]为基准，将<它的值放在它左边， >它的值放在它右边，并交换<=与>= 它的值的位置,使其均匀分布
    private static <E extends Comparable<E>> int partition2(E[] arr, int l, int r, Random rnd) {

        //双路快速排序法
        //优化2 解决如果数组含有大量相同元素
        //生成[l, r]之间的随机索引
        int p = l + rnd.nextInt( r - l + 1);
        swap(arr, l , p);

        int i = l + 1, j = r;

        // arr [l+1...i-1] <= v, arr[j+1...r] >= v
        while (true) {
            while (i <= j && arr[i].compareTo(arr[l]) < 0)
                i ++;
            while (j >= i && arr[j].compareTo(arr[l]) > 0 )
                j --;

            if (i >= j) break;
            swap(arr, i , j);
            i ++;
            j --;
        }

        swap(arr, l , j);
        return j;
    }

partition2.1

partition2.2

partition2.3

partition2.4

三路快速排序法：

进一步优化解决，数组中含有大量相同数据时与标准值相等的不进行处理，且当数组是完全相同过的时候复杂度为O(n)

示例(Java)

    //三路快速排序 解决数组中含有大量相同的元素尤其是完全相同数组
    //以arr[l]为基准，将<它的值放在它左边， >它的值放在它右边，=它的值放在中间
    private  static <E extends Comparable<E>> void sort3(E[] arr, int l, int r, Random rnd) {
        if (l >= r) return;

        //随机选择一个标准值
        int p = l + rnd.nextInt(r - l + 1);
        swap(arr, l, p);

        // arr[l+1, lt] < v, arr[lt+1, i-1] == v, arr[gt, r] > v
        int lt = l, i = l + 1, gt = r + 1;

        while (i < gt) {
            if (arr[i].compareTo(arr[l]) < 0) {
                lt ++ ;
                swap(arr, i , lt);
                i ++;
            } else if (arr[i].compareTo(arr[l]) > 0) {
                gt --;
                swap(arr, i, gt);
            } else { // arr[i] == arr[l]
                i ++;
            }
        }
        swap(arr, l , lt);

        // arr[l, lt-1] < v, arr[lt, gt - 1] == v, arr[gt, r] > v
        sort3(arr, l, lt - 1, rnd);
        sort3(arr, gt, r, rnd);
    }