[原]12-Python3实用教程-排序算法-快速排序

快速排序

快速排序的最坏运行情况是 O(n²),比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn),且 O(nlogn) 记号中隐含的常数因子很小,比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以,对绝大多数顺序性较弱的随机数列而言,快速排序总是优于归并排序。

对于一个长度为N的列表,排序步骤:

1、选择一个元素作为基准(可以选中间一个元素作为基准值),排序列表,使得比基准小的元素排在基准前面,比基准大的元素排在基准后面。这样这个基准的位置就确定了。

2、再对基准前面的列表和基准后面的列表,重复第一步操作。一次确定一个元素的位置

代码实现:

def sort(list):
    if len(list) < 2:
        return list
    mid = list[len(list) // 2]
    left, right = [], []
    list.remove(mid)
    for item in list:
        if item >= mid:
            right.append(item)
        else:
            left.append(item)
    # 使用迭代进行比较
    return sort(left) + [mid] + sort(right)

seq_list = [8, 6, 4, 9, 7, 3, 2, -4, 0, -100, 99]

print(sort(seq_list))
#[-100, -4, 0, 2, 3, 4, 6, 7, 8, 9, 99]
分享 提问
comments powered by Disqus