跳到主要内容

快速排序

快速排序（Quick Sort）是一种高效的排序算法，由英国计算机科学家 Tony Hoare 于 1959 年提出。它采用分治法（Divide and Conquer）策略，通过递归地将数组分为较小和较大的两部分来实现排序。快速排序的平均时间复杂度为 O(n log n)，在实际应用中表现优异。

快速排序的基本原理​

快速排序的核心思想是选择一个“基准值”（Pivot），然后将数组分为两部分：一部分包含比基准值小的元素，另一部分包含比基准值大的元素。接着，递归地对这两部分进行排序，最终合并成一个有序数组。

步骤分解​

  1. 选择基准值：从数组中选择一个元素作为基准值（通常选择第一个、最后一个或中间的元素）。
  2. 分区操作：将数组重新排列，使得比基准值小的元素位于基准值的左侧，比基准值大的元素位于右侧。
  3. 递归排序：对基准值左侧和右侧的子数组分别递归调用快速排序。
  4. 合并结果：由于分区操作已经保证了左侧和右侧的有序性，最终数组自然有序。
提示

快速排序的性能高度依赖于基准值的选择。如果基准值选择不当（例如总是选择最小或最大元素），算法可能退化为 O(n²) 的时间复杂度。

代码示例​

以下是一个用 Python 实现的快速排序示例：

python
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]  # 选择中间元素作为基准值
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

# 示例输入
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print("排序后的数组:", sorted_arr)

输入：[3, 6, 8, 10, 1, 2, 1]
输出：[1, 1, 2, 3, 6, 8, 10]

备注

上述代码使用了列表推导式来简化分区操作，但实际实现中可以通过原地交换（In-place）来优化空间复杂度。

分区操作的详细解释​

分区操作是快速排序的核心步骤。以下是一个原地分区的实现：

python
def partition(arr, low, high):
    pivot = arr[high]  # 选择最后一个元素作为基准值
    i = low - 1  # i 是较小元素的索引
    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  # 返回基准值的索引

def quick_sort_inplace(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)  # 获取分区索引
        quick_sort_inplace(arr, low, pi - 1)  # 递归排序左半部分
        quick_sort_inplace(arr, pi + 1, high)  # 递归排序右半部分

# 示例输入
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort_inplace(arr, 0, len(arr) - 1)
print("排序后的数组:", arr)

输入：[3, 6, 8, 10, 1, 2, 1]
输出：[1, 1, 2, 3, 6, 8, 10]

警告

原地分区实现虽然节省了空间，但需要小心处理索引边界，否则可能导致数组越界或无限递归。

快速排序的时间复杂度​

  • 平均情况：O(n log n)
  • 最坏情况：O(n²)（当每次选择的基准值都是最小或最大元素时）
  • 空间复杂度：O(log n)（递归栈的深度）
提示

通过随机选择基准值或使用“三数取中”法，可以显著降低最坏情况发生的概率。

实际应用场景​

快速排序广泛应用于需要高效排序的场景，例如：

  1. 数据库排序：对大量数据进行快速检索和排序。
  2. 编程语言内置排序函数：如 Python 的 sorted() 和 Java 的 Arrays.sort() 都使用了快速排序的变体。
  3. 算法竞赛：在时间限制严格的场景下，快速排序是常用的选择。

总结​

快速排序是一种高效且广泛使用的排序算法，其核心思想是通过分治法将问题分解为更小的子问题。尽管最坏情况下的时间复杂度为 O(n²)，但通过优化基准值的选择，可以显著提高性能。掌握快速排序不仅有助于理解分治法，还能为学习更复杂的算法打下基础。

附加资源与练习​

  • 练习 1：尝试用其他编程语言（如 Java 或 C++）实现快速排序。
  • 练习 2：修改代码，使其支持降序排序。
  • 练习 3：研究并实现“三数取中”法来选择基准值，观察其对性能的影响。
注意

在实现快速排序时，务必注意递归深度和数组边界，避免栈溢出或无限循环。

希望本文能帮助你理解快速排序的原理和应用！如果你有任何问题，欢迎在评论区留言。