JAVA十大排序算法之快速排序详解

目录

• 快速排序
  • 问题
  • 思路
  • 荷兰国旗问题
  • 代码实现
  • 时间复杂度
  • 算法稳定性
• 总结

public class QuickSort {
    public static final int[] ARRAY = {8, 5, 6, 4, 3, 1, 7, 2};
    public static final int[] ARRAY2 = {8, 3, 6, 2, 5, 1, 7, 5};
    private static int[] sort(int[] array, int left, int right) {
        if (array.length < 1 || left > right) return null;
        //拆分
        int partitionIndex = partition(array, left, right);
        //递归
        if (partitionIndex > left) {
            sort(array, left, partitionIndex - 1);
        }
        if (partitionIndex < right) {
            sort(array, partitionIndex + 1, right);
        }
        return array;
    }
    /**
     * 分区快排操作
     *
     * @param array 原数组
     * @param left  左侧头索引
     * @param right 右侧尾索引
     * @return 分区指示器  最后指向基准数
     */
    public static int partition(int[] array, int left, int right) {
        //基准数下标---随机方式取值，也就是数组的长度随机1-8之间
        int pivot = (int) (left + Math.random() * (right - left + 1));
        //分区指示器索引
        int partitionIndex = left - 1;
        //基准数和尾部元素交换
        swap(array, pivot, right);
        //按照规定，如果当前元素大于基准数不做任何操作；
        //小于基准数，分区指示器右移，且当前元素的索引大于分区指示器，交换
        for (int i = left; i <= right; i++) {
            if (array[i] <= array[right]) {//当前元素小于等于基准数
                partitionIndex++;
                if (i > partitionIndex) {//当前元素的索引大于分区指示器
                    //交换
                    swap(array, i, partitionIndex);
                }
            }
        }
        return partitionIndex;
    }
    /**
     * 双向扫描排序
     */
    public static int partitionTwoWay(int[] array, int left, int right) {
        //基准数
        int pivot = array[right];
        //左分区指示器索引
        int leftIndex = left - 1;
        //右分区指示器索引
        int rightIndex = right;
        //索引
        int index = left;
        while (index < rightIndex) {
            //若当前元素大于基准数，右分区指示器左移一位，当前元素和右分区指示器所指元素交换，索引保持不变
            if (array[index] > pivot) {
                swap(array, index, --rightIndex);
            } else if (array[index] <= pivot) {//当前元素小于等于基准数时，左分割指示器右移一位，索引右移
                leftIndex++;
                index++;
                //当前元素小于等于左分区指示器所指元素，交换
                if (array[index] < array[leftIndex]) {
                    swap(array, index, leftIndex);
                }
            }
        }
        //索引和 L 指向同一个元素
        swap(array, right, rightIndex);
        return 1;
    }
    //交换
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }

    public static void main(String[] args) {
        print(ARRAY);
        System.out.println("============================================");
        print(sort(ARRAY, 0, ARRAY.length - 1));
        System.out.println("====================双向排序==================");
        print(ARRAY2);
        System.out.println("============================================");
        print(sort(ARRAY2, 0, ARRAY2.length - 1));
    }
}