算法解析

快速排序算法有两个核心点，分别为 哨兵划分 和 递归 。

哨兵划分：

以数组某个元素（一般选取首元素）为 基准数 ，将所有小于基准数的元素移动至其左边，大于基准数的元素移动至其右边。

如下图所示，为哨兵划分操作流程。通过一轮 哨兵划分 ，可将数组排序问题拆分为 两个较短数组的排序问题 （本文称之为左（右）子数组）。

1 / 9

递归：

对 左子数组 和 右子数组 分别递归执行 哨兵划分，直至子数组长度为 1 时终止递归，即可完成对整个数组的排序。

如下图所示，为示例数组 [2,4,1,0,3,5] 的快速排序流程。观察发现，快速排序和 二分法 的原理类似，都是以 $\log$ 时间复杂度实现搜索区间缩小。

代码

def quick_sort(nums, l, r):
    # 子数组长度为 1 时终止递归
    if l >= r: return
    # 哨兵划分操作
    i = partition(nums, l, r)
    # 递归左（右）子数组执行哨兵划分
    quick_sort(nums, l, i - 1)
    quick_sort(nums, i + 1, r)
    
def partition(nums, l, r):
    # 以 nums[l] 作为基准数
    i, j = l, r
    while i < j:
        while i < j and nums[j] >= nums[l]: j -= 1
        while i < j and nums[i] <= nums[l]: i += 1
        nums[i], nums[j] = nums[j], nums[i]
    nums[l], nums[i] = nums[i], nums[l]
    return i

# 调用
nums = [3, 4, 1, 5, 2]
quick_sort(nums, 0, len(nums) - 1)

算法特性

• 时间复杂度：

  • 最佳 $\Omega (N\log N)$ ： 最佳情况下， 每轮哨兵划分操作将数组划分为等长度的两个子数组；哨兵划分操作为线性时间复杂度 $O(N)$ ；递归轮数共 $O(\log N)$ 。

  • 平均 $\Theta (N\log N)$ ： 在随机输入数组下，哨兵划分操作的递归轮数也为 $O(\log N)$ 。

  • 最差 $O(N^2)$ ： 在某些特殊输入数组下，每轮哨兵划分操作都将长度为 $N$ 的数组划分为长度为 $1$ 和 $N-1$ 的两个子数组，此时递归轮数达到 $N$ 。

    通过 「随机选择基准数」优化，可尽可能避免出现最差情况，详情请见下文。

• 空间复杂度 $O(N)$ ： 快速排序的递归深度最好与平均皆为 $\log N$ ；输入数组完全倒序下，达到最差递归深度 $N$ 。

  通过「Tail Call」优化，可将最差空间复杂度降低至 $O(\log N)$ ，详情请见下文。

• 虽然平均时间复杂度与「归并排序」和「堆排序」一致，但在实际使用中快速排序 效率更高 ，这是因为：

  • 最差情况稀疏性： 虽然快速排序的最差时间复杂度为 $O(N^2)$ ，差于归并排序和堆排序，但统计意义上看，这种情况出现的机率很低。大部分情况下，快速排序以 $O(N\log N)$ 复杂度运行。
  • 缓存使用效率高： 哨兵划分操作时，将整个子数组加载入缓存中，访问元素效率很高；堆排序需要跳跃式访问元素，因此不具有此特性。
  • 常数系数低： 在提及的三种算法中，快速排序的 比较、赋值、交换 三种操作的综合耗时最低（类似于插入排序快于冒泡排序的原理）。

• 原地： 不用借助辅助数组的额外空间，递归仅使用 $O(\log N)$ 大小的栈帧空间。

• 非稳定： 哨兵划分操作可能改变相等元素的相对顺序。

• 自适应： 若每轮哨兵划分操作都将长度为 $N$ 的数组划分为长度 $1$ 和 $N-1$ 两个子数组，则时间复杂度劣化至 $O(N^2)$ 。

算法优化

快速排序的常见优化手段有「Tail Call」和「随机基准数」两种。

Tail Call ：

由于普通快速排序每轮选取「子数组最左元素」作为「基准数」，因此在输入数组 完全倒序 时， partition() 的递归深度会达到 $N$ ，即 最差空间复杂度 为 $O(N)$ 。

每轮递归时，仅对 较短的子数组 执行哨兵划分 partition() ，就可将最差的递归深度控制在 $O(\log N)$ （每轮递归的子数组长度都 $\le$ 当前数组长度），即实现最差空间复杂度 $O(\log N)$ 。

代码仅需修改 quick_sort() 方法，其余方法不变，在此省略。

def quick_sort(nums, l, r):
    # 子数组长度为 1 时终止递归
    while l < r:
        # 哨兵划分操作
        i = partition(nums, l, r)
        # 仅递归至较短子数组，控制递归深度
        if i - l < r - i:
            quick_sort(nums, l, i - 1)
            l = i + 1
        else:
            quick_sort(nums, i + 1, r)
            r = i - 1

随机基准数：

同样地，由于快速排序每轮选取「子数组最左元素」作为「基准数」，因此在输入数组 完全有序 或 完全倒序 时， partition() 每轮只划分一个元素，达到最差时间复杂度 $O(N^2)$ 。

因此，可使用 随机函数 ，每轮在子数组中随机选择一个元素作为基准数，这样就可以极大概率避免以上劣化情况。

值得注意的是，由于仍然可能出现最差情况，因此快速排序的最差时间复杂度仍为 $O(N^2)$ 。

代码仅需修改 partition() 方法，其余方法不变，在此省略。

def partition(nums, l, r):
    # 在闭区间 [l, r] 随机选取任意索引，并与 nums[l] 交换
    ra = random.randrange(l, r + 1)
    nums[l], nums[ra] = nums[ra], nums[l]
    # 以 nums[l] 作为基准数
    i, j = l, r
    while i < j:
        while i < j and nums[j] >= nums[l]: j -= 1
        while i < j and nums[i] <= nums[l]: i += 1
        nums[i], nums[j] = nums[j], nums[i]
    nums[l], nums[i] = nums[i], nums[l]
    return i