快速排序

难度：⭐⭐⭐

1. 题目描述

题目描述

• 快速排序（Quick sort）算法使用分治法策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。
• 递归法步骤：
  1. 选择基准值：任意挑一个，简单点使用第一个或最后一个
  2. 以基准值为基准将序列划分为两个子序列
  3. 递归执行第 2 步

2. 关键点

• 以基准值为基准将序列划分为两个子序列

3. 代码实现

点击显示代码

import random


def sort_quick(lst):
    """快速排序"""
    if len(lst) <= 1:
        return lst
    m = lst[0]
    left = [x for x in lst if x < m]
    middle = [x for x in lst if x == m]
    right = [x for x in lst if x > m]
    return sort_quick(left) + middle + sort_quick(right)


lst = [random.randint(0, 10) for i in range(10)]
print(lst)
lst2 = sort_quick(lst)
print(lst2)

4. 运行示例

[6, 1, 0, 9, 3, 7, 1, 5, 8, 10]
[0, 1, 1, 3, 5, 6, 7, 8, 9, 10]

5. 进阶思考

1. 优化示例代码