4. 快速排序

目录

1. 4. 快速排序
   1. 目录
   2. 本章内容

本章内容

1. 学习分而治之
   1. 有时候，你可能会遇到使用任何已知的算法都 无法解决的问题。优秀的算法学家遇到这种问题时，不会就此 放弃，而是尝试使用掌握的各种问题解决方法来找出解决方 案。分而治之是你学习的第一种通用的问题解决方法。
2. 学习快速排序
   1. 一种常用的优雅的排序算法。快速排序使用 分而治之的策略。

前一章深入介绍了递归，本章的重点是使用学到的新技能来解决问题。 我们将探索分而治之 （divide and conquer，D&C）——一种著名的递归 式问题解决方法。

本书将深入算法的核心。只能解决一种问题的算法毕竟用处有限，而 D&C提供了解决问题的思路，是另一个可供你使用的工具。面对新问题 时，你不再束手无策，而是自问：“使用分而治之能解决吗？”

在本章末尾，你将学习第一个重要的D&C算法——快速排序。快速排序 是一种排序算法，速度比第2章介绍的选择排序快得多，实属优雅代码 的典范。

def quick_sort(arr):
    """
    快速排序算法

    参数:
        arr: 待排序的数组

    返回值:
        排序后的数组
    """

    # 递归基线：如果数组为空或只有一个元素，则已经排序
    if len(arr) < 2:
        return arr

    # 选择最后一个元素作为主元
    pivot = arr[-1]

    # 将数组分成小于主元、等于主元和大于主元的三部分
    less = [i for i in arr[:-1] if i <= pivot]
    equal = [i for i in arr[:-1] if i == pivot]
    greater = [i for i in arr[:-1] if i > pivot]

    # 递归排序小于主元和大于主元的子数组
    # 并将排序后的结果与等于主元的子数组合并
    return quick_sort(less) + equal + quick_sort(greater)

# 测试代码
test_array = [3, 7, 8, 5, 2, 1, 9, 5, 4]
sorted_array = quick_sort(test_array)
print(f"排序后的数组：{sorted_array}")