Python 快速排序算法指南

探索 Python 中的快速排序算法。在此交互式编码示例中学习主元选择、分区和递归。

在编辑器中尝试

概述

快速排序是一种极其快速且广泛使用的排序算法。与合并排序一样，它采用分而治之的方法。然而，快速排序对元素进行“就地”排序，从而提高内存效率。

该算法的工作原理是从列表中选择一个“枢轴”元素。然后，它将其他元素划分为两个子数组：小于主元的子数组和大于主元的子数组。该过程递归地应用于子数组。

尽管快速排序的最坏情况复杂度为 O(n²)，但其平均情况运行时间为 O(n log n)，并且由于缓存未命中率较低且创建临时数组的开销为零，因此在实践中它通常优于合并排序。

代码和执行输出

一个简洁的递归快速排序脚本，使用列表推导来实现高可读性。

quicksort.py

在编辑器中尝试

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    else:
        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 quicksort(left) + middle + quicksort(right)

# Test list
data = [12, 4, 5, 6, 7, 3, 1, 15]
print("Original List:", data)
sorted_data = quicksort(data)
print("Sorted List:  ", sorted_data)

端子输出

Original List: [12, 4, 5, 6, 7, 3, 1, 15]
Sorted List:   [1, 3, 4, 5, 6, 7, 12, 15]

逐步实施

内存占用必须保持在最低限度的系统排序例程
标准语言库框架中的通用排序
分治力学与递归分而治之学术教学

常见问题解答

我们如何避免快速排序中 O(n²) 的最坏情况复杂度？

最坏的情况发生在所选主元重复为最小或最大元素时。为了缓解这种情况，开发人员使用选择随机主元或“三中位数”值等策略。

快速排序稳定吗？

不，标准快速排序是不稳定的。在分区期间，元素在长范围内交换，这可能会改变重复元素的相对顺序。