8、快速排序-JZTXT

1、单路快速排序

单路快速排序：O(N * logN)
当数组中的元素一致时退化为 O(n²)

public class QuickSort {

    private static final Random RANDOM = new Random();

    private QuickSort() {
    }

    /**
     * 快速排序
     */
    public static <E extends Comparable<E>> void sort(E[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    /**
     * 快速排序 arr[l, r]
     */
    private static <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
        if (r - l <= 15) {
            InsertionSort.sort(arr, l, r);
            return;
        }

        int p = partition(arr, l, r);

        sort(arr, l, p - 1);
        sort(arr, p + 1, r);
    }

    /**
     * 单路快排
     */
    private static <E extends Comparable<E>> int partition(E[] arr, int l, int r) {
        int p = RANDOM.nextInt(r - l + 1) + l;
        swap(arr, l, p);

        E v = arr[l];
        int j = l;

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

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

    private static <E> void swap(E[] arr, int a, int b) {
        E k = arr[a];
        arr[a] = arr[b];
        arr[b] = k;
    }
}

2、双路快速排序

双路快速排序：O(N * logN)

public class QuickSort {

    private static final Random RANDOM = new Random();

    private QuickSort() {
    }

    /**
     * 快速排序
     */
    public static <E extends Comparable<E>> void sort(E[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    /**
     * 快速排序 arr[l, r]
     */
    public static <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
        if (r - l <= 15) {
            InsertionSort.sort(arr, l, r);
            return;
        }

        int p = partition(arr, l, r);

        sort(arr, l, p - 1);
        sort(arr, p + 1, r);
    }

    /**
     * 双路快排
     */
    public static <E extends Comparable<E>> int partition(E[] arr, int l, int r) {
        int p = RANDOM.nextInt(r - l + 1) + l;
        swap(arr, l, p);

        E v = arr[l];
        int p1 = l + 1;
        int p2 = r;

        // arr[l, p1 - 1] >= v, arr[p2 + 1, r] <= v
        // 循环结束的 2 种情况: p1 > p2 和 p1 == p2
        while (true) {
            while (p1 <= p2 && arr[p1].compareTo(v) < 0) p1++; // arr[p1] >= v
            while (p1 <= p2 && arr[p2].compareTo(v) > 0) p2--; // arr[p2] <= v

            if (p1 >= p2) break; // 也可以理解为当 p1 >= p2 时, 就没必要 swap(arr, p1, p2) 了

            swap(arr, p1++, p2--);
        }

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

    public static <E> void swap(E[] arr, int a, int b) {
        E k = arr[a];
        arr[a] = arr[b];
        arr[b] = k;
    }
}

3、三路快速排序

三路快速排序：O(N * logN)
所有元素都相同的数组 O(n)

public class QuickSort {

    private static final Random RANDOM = new Random();

    private QuickSort() {
    }

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

    private static <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
        if (r - l <= 15) {
            InsertionSort.sort(arr, l, r);
            return;
        }

        int[] p = partition(arr, l, r);

        sort(arr, l, p[0]);
        sort(arr, p[1], r);
    }

    private static <E extends Comparable<E>> int[] partition(E[] arr, int l, int r) {
        int p = RANDOM.nextInt(r - l + 1) + l;
        swap(arr, l, p);

        E v = arr[l];
        int p1 = l;
        int p2 = r + 1;

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

        // arr[l + 1, p1] < v, arr[p2, r] > v
        int i = l + 1;
        while (i < p2) {
            if (arr[i].compareTo(v) < 0) swap(arr, ++p1, i++);
            else if (arr[i].compareTo(v) > 0) swap(arr, --p2, i);
            else i++;
        }
        
        swap(arr, l, p1);
        return new int[]{p1 - 1, p2};
    }

    private static <E> void swap(E[] arr, int a, int b) {
        E k = arr[a];
        arr[a] = arr[b];
        arr[b] = k;
    }
}

4、Partition 总结

单路快速排序法：完全有序的数据退化，因此引入随机化，但是具有大量重复元素的数据退化
双路快速排序法：可以让一样的数据比较平均的分配到左右两边
三路快速排序法：对完全重复的数据排序，复杂度为 O(n)

	单路	双路	三路
随机数据	✓	✓	✓
有序数据	✓	✓	✓
重复数据	×	✓	O(n)