CC++ & Algorithm

Python快速排序

困难5
语言版本：C++Python
概述：快速排序像排队游戏，选一个“标杆”，高的站右边，矮的站左边，然后分别对左右两边重复操作。

快速排序：像排队游戏一样给数字排队

快速排序是一种非常经典的排序算法，它像我们平时玩的一个排队游戏——先选一个“队长”，然后让比他矮的站左边，比他高的站右边，接着对左边和右边的小队分别重复同样的操作，直到每队只有一个人，整个队伍就排好了。这种“分而治之”的思想叫分治算法，快速排序就是分治思想最典型的应用之一。它比归并排序更常用，因为在大多数情况下它跑得飞快，而且代码写起来也很简洁。

生活中的排队游戏

想象体育课上老师让大家按身高从矮到高排队。老师没有直接测量每个人的身高，而是想了个办法：先随便叫一个同学（比如小明）站出来当“标杆”，然后其他同学自动分成两群——身高比小明矮的站到小明左边，比小明高的站到小明右边，和小明一样高的就随便站（通常我们站在左边或右边都行）。这样一来，小明就站到了正确的位置上（比矮的高、比高的矮）。接下来，老师对左边那堆同学再重复同样的方法，挑一个新标杆，继续分；对右边那堆也重复。直到每个小堆只剩下一个人，那么所有人的位置就都正确了。

这个游戏其实就是快速排序的直观过程。在计算机里，我们有一堆杂乱无章的数字，想按从小到大排序，就可以用这个“选标杆、分两边”的方法。

快速排序的核心步骤

1. 选择基准（pivot）

从数组中随便选一个元素当作“标杆”。通常最简单的方法是选第一个元素或者最后一个元素。当然，选基准的技巧会影响排序效率，但初学阶段我们先用第一个元素。

2. 分区（partition）

这是快速排序最关键的一步。把数组中剩下的元素（除了基准）分成两部分：所有比基准小的元素放到基准左边，所有比基准大的元素放到基准右边。基准最终放在中间位置，这样基准就找到了它最终的正确位置。

3. 递归（recursion）

对基准左边和右边的子数组重复上面的步骤，直到每个子数组只剩下一个元素（或者为空）。递归停止时，整个数组就排好序了。

用卡片排序的例子理解

假设你手里有5张数字卡片：[5, 3, 8, 4, 2]，想要从小到大排好。

  • 第一轮：选第一个数 5 作为基准。
    看剩下的卡片：3、8、4、2。
    比5小的有：3、4、2，把它们放到左边。
    比5大的有：8，放到右边。
    左边得到 [3, 4, 2]，右边得到 [8]，基准放在中间。
    现在的顺序是：[3, 4, 2] 5 [8]。

  • 第二轮：处理左边的 [3, 4, 2]。选第一个 3 为基准。
    比3小的有：2 → 左边 [2]。
    比3大的有：4 → 右边 [4]。
    得到 [2] 3 [4]。
    右边 [8] 只有一个元素，不用再排了。

  • 第三轮：处理 [2] 和 [4] 都已经只有一个元素，排序结束。

最后把左右全部合并：左边 2，中间 3，右边 4，再加上之前的 5 和 8，得到 [2, 3, 4, 5, 8]，排序完成。

Python代码实现：易理解的“创建新列表”版本

对于初学者来说，最容易理解的方式就是每次递归都创建新的列表来保存左边和右边的元素，然后拼接起来。下面的代码中，变量都用简单的英文单词，每一行都写上了中文注释。

def quick_sort(arr):
    # 基准情况：空列表或只有一个元素，直接返回
    if len(arr) <= 1:
        return arr

    # 选择第一个元素作为基准
    pivot = arr[0]

    # 分区：创建两个新列表，分别存放比基准小和比基准大的元素
    left = [x for x in arr[1:] if x < pivot]   # 所有比pivot小的数
    right = [x for x in arr[1:] if x > pivot]  # 所有比pivot大的数
    # 注意：等于pivot的元素我们没有单独处理，它们会被忽略？其实不会，因为基准只有一个，
    # 但如果有重复元素，这样会把重复的弄丢。所以更稳妥的做法是：把等于pivot的也收集起来。
    # 但为了简单，我们先假设没有重复，或者我们单独加一个middle列表。
    # 实际上我们可以这样：middle = [x for x in arr[1:] if x == pivot] 再拼接。
    # 为了更准确且不改变原意，下面我们用一种更通用的写法：

    # 更好的分区方式：小于、等于、大于
    left = [x for x in arr[1:] if x < pivot]    # 比基准小
    middle = [x for x in arr[1:] if x == pivot] # 等于基准（可能多个）
    right = [x for x in arr[1:] if x > pivot]   # 比基准大

    # 递归排序左边和右边，然后合并
    return quick_sort(left) + [pivot] + middle + quick_sort(right)

# 测试一下
test_list = [33, 10, 55, 71, 29, 47, 8]
sorted_test = quick_sort(test_list)
print(sorted_test)  # 输出: [8, 10, 29, 33, 47, 55, 71]

注意：上面的代码中，我们特别加了一个middle列表，用来收集和基准相等的元素。这样即使数组中有多个相同的数字，也不会丢失。原来的写法left + [pivot] + right只包含了一个基准，会丢失重复的相等元素。

常见错误与注意事项

错误1：忘记处理相等元素
如果数组中有重复数字，只把基准放在中间，那么等于基准的其他元素就会被丢掉。例如 [5, 3, 5, 2]，基准选第一个5，剩下的有3、5、2。比5小的有3、2，比5大的没有，但还有一个等于5的元素没有被放到任何一边。所以排序结果会变成 [2, 3, 5]，漏掉了一个5。正确做法是单独收集等于基准的元素并一起放中间。

错误2：基准选择不当导致递归过深
如果每次选的基准都是数组里最小或最大的元素，那么分区后一边为空，另一边有n-1个元素，导致递归深度变成n，时间复杂度退化成O(n²)。比如已经排好序的数组 [1,2,3,4,5]，如果每次都选第一个为基准，那么每次左边为空，右边有剩下的所有数，效率很低。解决方法是采用“三数取中”技巧：取数组的第一个、中间、最后一个元素，选出中间大小的那个作为基准，或者随机选一个基准（random.choice(arr)）。对于初学者，先理解思想，再慢慢了解优化。

错误3：忘记递归终止条件
如果没写 if len(arr) <= 1: return arr，函数会无限递归下去，直到栈溢出程序崩溃。所以基准情况一定要写对。

错误4：误以为原地交换版本很难
上面的版本每次递归都会创建新列表，占用额外内存。真正的快速排序会采用“原地分区”的方式，只用常数级的额外空间，但代码稍微复杂一些。如果你已经掌握了递归思想，可以尝试挑战一下原地交换版本（后面会给出参考代码）。

完整可运行的示例（含测试和输出）

下面是包含测试代码的完整程序，你可以直接复制到Python环境运行。

def quick_sort(arr):
    """
    快速排序（创建新列表版）
    :param arr: 待排序的列表
    :return: 排序后的新列表
    """
    if len(arr) <= 1:
        return arr

    pivot = arr[0]  # 选第一个元素为基准

    # 分别收集比基准小、等于、大的元素
    left = [x for x in arr[1:] if x < pivot]    # 小的放左边
    middle = [x for x in arr[1:] if x == pivot] # 相等的放中间
    right = [x for x in arr[1:] if x > pivot]   # 大的放右边

    # 递归排序左右部分，然后拼接
    return quick_sort(left) + [pivot] + middle + quick_sort(right)

# 测试不同情况
if __name__ == "__main__":
    # 测试1：普通乱序
    scores = [88, 72, 93, 65, 81, 77, 90]
    print("原始成绩:", scores)
    sorted_scores = quick_sort(scores)
    print("排序后成绩:", sorted_scores)

    # 测试2：包含重复数字
    numbers = [4, 2, 4, 1, 3, 2, 4]
    print("\n原始数字:", numbers)
    sorted_numbers = quick_sort(numbers)
    print("排序后数字:", sorted_numbers)

    # 测试3：已经排好序的数组（注意效率会变差，但结果正确）
    ordered = [10, 20, 30, 40, 50]
    print("\n原始有序数组:", ordered)
    sorted_ordered = quick_sort(ordered)
    print("排序后:", sorted_ordered)

    # 测试4：空列表和单元素列表
    empty_list = []
    single = [7]
    print("\n空列表排序:", quick_sort(empty_list))  # []
    print("单元素列表排序:", quick_sort(single))    # [7]

运行结果：

原始成绩: [88, 72, 93, 65, 81, 77, 90]
排序后成绩: [65, 72, 77, 81, 88, 90, 93]

原始数字: [4, 2, 4, 1, 3, 2, 4]
排序后数字: [1, 2, 2, 3, 4, 4, 4]

原始有序数组: [10, 20, 30, 40, 50]
排序后: [10, 20, 30, 40, 50]

空列表排序: []
单元素列表排序: [7]

如果你想更进一步：原地交换版本（选学）

对于已经熟练掌握递归和列表操作的同学，可以看看这个原地交换的实现，它不创建新列表，而是在原列表上直接调整元素位置。这个版本更接近真实的快速排序。

def partition(arr, low, high):
    """
    原地分区函数：以arr[high]为基准，把小于基准的移到左边，大于的移到右边，
    返回基准最终位置的索引
    """
    pivot = arr[high]          # 选最后一个元素作为基准
    i = low - 1                # i 指向已处理区的最后一个位置

    for j in range(low, high): # j 遍历待处理区
        if arr[j] <= pivot:    # 如果当前元素 <= 基准
            i += 1             # 扩大已处理区
            arr[i], arr[j] = arr[j], arr[i]  # 交换，把小的元素换到左边

    # 把基准放到正确位置（i+1）
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quick_sort_inplace(arr, low, high):
    """原地快速排序递归函数"""
    if low < high:
        # 分区，得到基准位置 pi
        pi = partition(arr, low, high)
        # 递归排序左边和右边
        quick_sort_inplace(arr, low, pi - 1)
        quick_sort_inplace(arr, pi + 1, high)

# 测试原地版本
my_list = [33, 10, 55, 71, 29, 47, 8]
quick_sort_inplace(my_list, 0, len(my_list) - 1)
print("原地排序结果:", my_list)

原地版本更节省内存，但理解起来需要你熟悉交换和指针移动。初学阶段可以先掌握创建新列表的版本，以后再挑战。

快速排序的时间复杂度

  • 最好情况：每次基准都能把数组分成均匀的两半 → O(n log n)
  • 最坏情况：每次基准都是最大或最小 → O(n²)
  • 平均情况：随机数据 → O(n log n)

虽然最坏情况存在，但通过随机选择基准或三数取中，实际应用中几乎不会遇到最坏情况。快速排序因此成为大多数编程语言内置排序函数的首选（如Python的sorted底层其实用了Timsort，是一种结合快速排序和归并排序的混合算法，但思想相通）。

相关指引：学完快速排序后可以看什么？

  1. 归并排序：也是分治思想，但它是从中间切分，保证稳定排序，适合链表或外部排序。
  2. 分治算法：快速排序、归并排序、二分查找、快速幂都是分治思想的经典应用。
  3. 选择排序与插入排序：简单但效率低的排序，可以对比理解快速排序的优势。
  4. Python内置排序：试试 sorted() 和 list.sort()，看看它们底层是如何实现的。

快速排序就像排队游戏一样，先找标杆，再分左右，反复进行，最终整个队伍井然有序。希望大家通过这个游戏，牢牢记住分治思想，并能自己写出漂亮的快速排序代码！

例题精讲

1单选题

快速排序在平均情况下的时间复杂度是？

AO(n)
BO(n log n)
CO(n^2)
DO(log n)
2单选题

在快速排序中，如果每次选择第一个元素作为基准，且输入的数组已经按升序排列，那么该快速排序的时间复杂度为？

AO(n)
BO(n log n)
CO(n^2)
DO(log n)
3判断题

快速排序是一种稳定的排序算法。

4填空题
以下为快速排序的分区函数（Lomuto分区方案），请在空白处填入正确内容。

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] ___ pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i+1
5填空题
以下为快速排序的递归函数，请在空白处填入正确内容（每处空白填写一个表达式）。

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, ___ )
        quick_sort(arr, ___ , high)