Python实现快速排序算法详解

本文旨在帮助读者深入理解快速排序算法，并提供 Python 语言的实现示例。快速排序（Quicksort）是一种高效的排序算法，由 C.A.R. Hoare 在 1962 年提出，是对冒泡排序的一种改进。

快速排序属于分治策略的应用，其核心思想是在数据集之中选择一个元素作为“基准”（pivot），所有小于基准的元素移动到基准前面，所有大于基准的元素移动到基准后面，然后递归地在两个子区间上应用相同的方法。

具体步骤如下：

1. 从数列中挑出一个元素，称为“基准”。
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割（partition）操作。
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

下面是 Python 语言实现快速排序的一个示例：

def quick_sort(arr, low, high):
    if low         pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)  # 递归排序左子数组
        quick_sort(arr, pi + 1, high)  # 递归排序右子数组

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

# 测试代码
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quick_sort(arr, 0, n - 1)
print("排序后的数组:", arr)

快速排序的时间复杂度在平均情况下为 O(n log n)，在最坏的情况下为 O(n^2)，但这种最坏情况很少见。空间复杂度为 O(log n)，主要用于递归调用栈的空间消耗。

快速排序之所以高效，是因为它在每次递归过程中都能将问题规模显著减小。尽管在极端情况下（例如已经排序好的数组）其性能会下降，但在实际应用中，通过随机选择基准或使用三数取中法等技术，可以有效避免这种情况的发生。