首页 › Python 实例 › 快速排序

Python 快速排序

算法实例 040

题目

用分治思想实现快速排序:选一个基准值,把列表分成小于、等于、大于基准的三部分,再递归排序。

参考代码

def quick_sort(items):
    if len(items) <= 1:
        return items
    pivot = items[len(items) // 2]
    left = [x for x in items if x < pivot]
    middle = [x for x in items if x == pivot]
    right = [x for x in items if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

data = [33, 10, 55, 71, 29, 10, 2, 90, 45]
print("排序前:", data)
print("排序后:", quick_sort(data))
执行以上代码输出结果为:
排序前: [33, 10, 55, 71, 29, 10, 2, 90, 45]
排序后: [2, 10, 10, 29, 33, 45, 55, 71, 90]

代码解析

这个版本代码清晰,便于理解思路,但会创建很多新列表。平均时间复杂度为 O(n log n)。