1. 思想

快速排序思想：

1. 首先选出一个基准值
2. 然后将小于基准值的数放在其左边，大于基准值的数放在其右边
3. 最后递归对左子序列和右子序列排序

2. 算法

1. 一直移动右指针，直到其值比基准值小
2. 然后把右指针的值给左指针
3. 一直移动左指针，直到其值比基准值大
4. 然后把左指针的值给右指针
5. 把基准值放在指针重合位置
6. 递归排序左子序列和右子序列

3. 代码

参考视频：https://www.bilibili.com/video/BV1at411T75o?from=search&seid=3646433316569041770

public static void quickSort(int[] array, int l, int r) {
    if (l >= r) {
        return;
    }

    int left = l;
    int right = r;
    int p = l;
    int pValue = array[p];

    while (left < right) {
        // 一定要先排右边，因为此时基准值取的左边
        while (left < right && array[right] > pValue) {
            right--;
        }
        if (left < right) {
            array[left] = array[right];
        }

        while (left < right && array[left] <= pValue) {
            left++;
        }
        if (left < right) {
            array[right] = array[left];
        }
    }

    array[left] = pValue;
    quickSort(array, l, left - 1);
    quickSort(array, left + 1, r);
}

PS：生成随机数组

int[] array = Stream.generate(() -> (int) (Math.random() * 100)).limit(10).mapToInt(x -> x).toArray();

4. 复杂度