Python 快速排序演算法指南

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

概述

快速排序是一種極為快速且廣泛使用的排序演算法。與合併排序一樣，它採用分而治之的方法。然而，快速排序对元素进行“就地”排序，从而提高内存效率。

该算法的工作原理是从列表中选择一个“枢轴”元素。然後，它將其他元素劃分為兩個子數組：小於主元的子數組和大於主元的子數組。该过程递归地应用于子数组。

Although Quicksort has a worst-case complexity of O(n²), its average-case runtime is O(n log n), and it typically outperforms merge sort in practice due to lower cache misses and zero temphead of creating tempyy .

程式碼和執行輸出

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

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²) 的最壞情況複雜度？

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

快速排序穩定嗎？

不，標準快速排序是不穩定的。在分區期間，元素在長範圍內交換，這可能會改變重複元素的相對順序。