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)。