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. 复杂度

算法平均时间复杂度最好最坏空间复杂度排序方式稳定性
快速排序$O(nlog_2n)$$O(nlog_2n)$$O(n^2)$$O(nlog_2n)$内部排序不稳定
Last modification:March 16th, 2021 at 09:25 am