十大排序算法之六：快速排序（Python）

快速排序

1. 算法步骤

1.1 从数列中挑出一个元素，称为“基准”（pivot）；
1.2 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆放在基准后面，相同的数可以摆放到任意一边。在这个分区退出之后，基准就会位于数列的中间位置，这个称为分区（partition）操作；
1.3 递归地（recursive）把小于基准值的子数列和大于基准值的子数列排序。

2. Python代码实现

def quick_sort(l):
    if len(l)<2:
        return l
    mid = l[len(l)//2]
    left, right = [], []
    l.remove(mid)
    for item in l:
        if item >= mid:
            right.append(item)
        else:
            left.append(item)
    return quick_sort(left) + [mid] + quick_sort(right)

l = [2,1,3,5,4]
print(quick_sort(l))

运行结果

[1, 2, 3, 4, 5]

3. Python列表推导式实现

def quick_sort(quick_list):
    if quick_list == []:
        return []
    else:
        mid = quick_list[0]
        left = quick_sort([l for l in quick_list[1:] if l<mid])
        right = quick_sort([r for r in quick_list[1:] if r>mid])
        return left + [mid] + right

quick_list = [2,1,3,5,4]
print(quick_sort(quick_list))

运行结果

[1, 2, 3, 4, 5]