快速排序的逻辑

用递归的方法：

1 边界条件，数组长度为1，返回list

2 list =( list_left )+ ( mid ) +( list_right )

注意个细节，mid是一个元素值，不是下标

 

# 快速排序
def quick_sort(l):
    if len(l) < 2:
        return l
    # 先取一个中间值
    mid = l.pop(len(l) // 2)
    left = []  # 存放小于m的数
    right = []  # 存放大于m的数
    for n in l:
        if n < mid:
            left.append(n)
        else:
            right.append(n)
    # print('left:',left)
    # print('right:',right)
    # 递归
    return quick_sort(left) + [mid] + quick_sort(right)  # 次一级的通项，公式，最重要


ll = [4, 5, 9, 7, 6, 8, 2, 1, 3]
print(quick_sort(ll))