[算法练习] 快速排序

参考资料
快速排序算法

image.png

    @Test
    public void test() {
        int[] array = new int[]{4, 2, 6, 8, 1, 4, 0, 7};
        quickSort(array, 0, array.length - 1);
        for (int i : array) {
            System.out.print(i + " ");
        }

    }

    private void quickSort(int[] array, int L, int R) {
        // 递归回溯语句
        if (L >= R) {
            return;
        }

        int left = L;
        int right = R;
        int pivot = array[left]; // 中心值

        while (left < right) {
            // 找到右侧比中心值小的数, 为了后面做调换
            while (left < right && array[right] >= pivot) {
                right--;
            }

            // 找到一个值 array[right] < pivot
            if (left < right) {
                array[left] = array[right];
            }

            // 找到左侧比中心值大的数, 为了后面做调换
            while (left < right && array[left] < pivot) {
                left++;
            }

            // 找到一个值 array[left] > pivot
            if (left < right) {
                array[right] = array[left];
            }
        }

        // left >= right, 如果left, right 交汇了就说明排序已完成, 所有的数字已经调整过
        array[left] = pivot;

        // 递归排序左边到中心值坐标的数组
        quickSort(array, L, right - 1);

        // 递归排序中心值坐标到右边的数组
        quickSort(array, right + 1, R);
    }