【快速排序】

快速排序

时间复杂度为 o(nlogn)

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

    private static <E extends Comparable<E>> void sort(E[] array, int left, int right) {
        if (left >= right)
            return;
        int p = partition(array, left, right);
        sort(array, left, p - 1);
        sort(array, p + 1, right);
    }

    private static <E extends Comparable<E>> int partition(E[] array, int left, int right) {
        //如果这个数组是有序的，从大到小，导致递归每次只减少一个元素，这样递归深度就是n,会栈溢出
        //所以随机一个位置数据，并替换到left位置
        int randomIndex = random.nextInt(right - left + 1) + left;
        swap(array, left, randomIndex);

        int j = left;
        //将[0,j]存放小于array[j]，[j+1,right]存放大于array[j]
        for (int i = left + 1; i <= right; i++) {
            if (array[i].compareTo(array[left]) < 0) {
                j++;
                E temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }

        swap(array, left, j);
        return j;
    }

2、双路快速排序

核心思路：

1. 先随机一个索引和最左边元素进行互换
2. 循环数组，将元素 分成小于等于v 和 大于等于v 三部分。
3. 其中 小于等于v 和 大于等于v 继续进行递归调用 1步骤执行。
4. 最终达到一个有序效果，

问题：如果是个等值数组，元素够多会造成栈溢出

    private static <E extends Comparable<E>> void twoWaySort(E[] array, int left, int right) {
        if (left >= right)
            return;

        int partition = twoPartition(array, left, right);
        twoWaySort(array, left, partition - 1);
        twoWaySort(array, partition + 1, right);
    }
    
    private static <E extends Comparable<E>> int twoPartition(E[] array, int left, int right) {
        //如果这个数组是有序的，从大到小，导致递归每次只减少一个元素，这样递归深度就是n,会栈溢出
        //所以随机一个位置数据，并替换到left位置；由于nextInt不含边界值所以加一
        int randomIndex = random.nextInt(right - left + 1) + left;
        swap(array, left, randomIndex);

        int i = left + 1, j = right;
        //将[left,i-1]存放 <= array[left]，[j+1,right]存放 >= array[left]
        while (true) {
            while (i <= j && array[i].compareTo(array[left]) < 0) {
                i++;
            }
            while (i <= j && array[j].compareTo(array[left]) > 0) {
                j--;
            }

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

        swap(array, left, j);
        return j;
    }

3、三路快速排序

核心思路：

1. 先随机一个索引和最左边元素进行互换
2. 循环数组，将元素 分成小于v 、等于v 和 大于v 三部分。
3. 其中 小于v 和 大于v 继续进行递归调用 1步骤执行。
4. 最终达到一个有序效果，

​

三路快速排序解决了 一个相同元素数组时间复杂度为 o(n²)问题，而一个有序数组时间复杂度为 o(n²) 解决方式则为使用左侧替换随机索引值解决。

public class SimpleQuickSort {

    private static final Random random = new Random();

    //方式三：三路快速排序
    public static <E extends Comparable<E>> void threeWaySort(E[] array) {
        threeWaySort(array, 0, array.length - 1);
    }

    private static <E extends Comparable<E>> void threeWaySort(E[] array, int left, int right) {
        if (left >= right)
            return;

        int randomIndex = random.nextInt(right - left + 1) + left;
        swap(array, left, randomIndex);

        //循环不变量： array[left+1,lt]<array[left]，array[lt+1,i-1]=array[left]，array[gt,r]>array[left]
        int lt = left, i = left + 1, gt = right + 1;
        while (i < gt) {
            if (array[i].compareTo(array[left]) < 0) {
                //小于array [left]
                lt++;
                swap(array, lt, i);
                i++;
            } else if (array[i].compareTo(array[left]) > 0) {
                //大于array [left]
                gt--;
                swap(array, i, gt);
            } else {
                //array[i] = array [left]
                i++;
            }
        }

        //替换left到等于array[left]位置
        //循环不变量： array[left+1,lt-1] < array[left]，array[lt,gt-1] = array[left]，array[gt,r] > array[left]
        swap(array, left, lt);

        threeWaySort(array, left, lt - 1);
        threeWaySort(array, gt, right);
    }

    private static <E extends Comparable<E>> void swap(E[] array, int i, int j) {
        E temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String[] args) {
        Integer[] arr = {4, 6, 5, 2, 3, 8, 7, 1};
        System.out.println(Arrays.toString(arr));
        threeWaySort(arr);
        System.out.println(Arrays.toString(arr));  }
    }
}