看图聊算法：快速排序的原理与实现

发表于 1年以前 | 总阅读数：588 次

在排序的算法中，1945 年由冯·诺依曼发明的归并排序（Merge Sort），是一种典型利用分治策略高效解决问题的算法。

看图聊算法：归并排序的原理与优化然而，归并排序的缺陷在于其需要额外存储空间。这引发了一个问题：能不能有一种算法，既不依赖额外空间，又能利用分治思想进行原地排序？

快速排序正是这样一种算法。不同于归并排序，快速排序将重心放在“分”上，让“治”自然发生。

快速排序的核心原理

快速排序分为两个核心过程组成：

划分（Partition）：选择数组中的一个元素为支点（pivot），通过一次遍历，将小于等于支点的元素移到左侧，大于支点的元素移动到右侧。递归（Recursion）：对左右两侧的子数组，重复执行上述操作，直到整个数组完全有序。

选择合适的支点（pivot）

我们首先来选择支点（pivot），支点的选择对快速排序的效率影响显著。

理想情况下，支点选择数组中位数，这样能确保划分后的子数组尽量平衡，从而最大限度地发挥分治的效果。

但在实际操作中，每次都去找中位数从性能上看，似乎划不来。因此，对于随机排列的数组，直接选择最后一个元素作为支点，不失为一种好方法。

划分（Partition）过程

选择好支点后，我们可以对数组进行划分操作，将小于等于支点的元素移到左侧，大于支点的元素移动到右侧。这也是快速排序算法中最重要的部分。

划分

在这一过程中，通过一次数组扫描并设置两个指针 i 和 j，确保在扫描过程中满足以下条件：

[lo, i] 之间的元素都 <=pivot。
[i+1, j-1] 之间的元素都 >pivot。
[j, hi-1] 之间的元素未被扫描。

划分扫描条件

扫描初始化：在扫描开始前，我们设置 i=lo-1 和 j=lo以保持上述三个条件成立。

这样，在初始状态下 [j, hi-1] 之间是所有未扫描的元素，[lo, i] (<=pivot) 和 [i+1, j-1] (>pivot) 的区间都不存在。划分扫描初始化扫描过程：

当 A[j] > pivot 时，j 的值加 1。保证 [i+1, j-1] 之间的元素 >piovt。

动图划分扫描过程 1当 A[j] <= pivot 时，i 加 1，交换 A[i] 和 A[j] 的值之后，j 再加 1。这样同时保证了 [lo, i] 之间的元素 <=pivot，并且 [i+1, j-1] 之间的元素 >piovt。

动图划分扫描过程

2扫描结束：扫描完成时，j = hi，此时我们需要将支点 A[hi] 置于正确位置。通过交换 A[hi] 与 A[i+1]，支点就位，返回其索引。

动图划分扫描结束

将上述的扫描过程转化为代码是一个有趣的挑战，你可以先思考一下如何实现。这里提供一个我编写的函数，以供参考：

def partition(A, lo, hi):
    pivot = A[hi]
    i = lo - 1
    for j in range(lo, hi):
        if A[j] <= pivot :
            i = i + 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[hi] = A[hi], A[i + 1]
    return i + 1

视频划分扫描执行过程

注意：你可以在我的 github 仓库中查看源代码

https://github.com/dingtingli/algorithm/blob/main/Code/quicksort01.py

递归：实现快速排序

我们来完成最后一步，通过递归不断地对子数组进行划分，直到每个子数组只有一个元素，整个数组就被排序完成。

def quicksort(A, lo, hi):
    if lo < hi:
        pivot_index = partition(A, lo, hi)
        quicksort(A, lo, pivot_index - 1)
        quicksort(A, pivot_index + 1, hi)

详细的递归执行过程示意图如下：