【动手学数据结构—快速排序（Python）】

快速排序

• 原理
• 代码实现

原理

代码实现

def paratition(li, left, right):
    temp = li[left]  # 用temp变量暂存第一个元素
    while left < right:  # 当left和right两个指标的位置没碰到时，继续更替
        while left < right and li[right] >= temp:  # 第一个条件防止right小于left 第二个条件则是查找的核心条件
            right -= 1  # 如果这个位置大于temp 则往上找
        li[left] = li[right] # 找到了！ 换
        while left < right and li[left] <= temp: # 与上一个while同理
            left += 1
        li[right] = li[left]
    li[left] = temp  # 最后更替到left与right重叠的时候，再把temp放回最中间，因为temp在列表中被拿走了
    return left  # 返回中心位置


def quick_sort(li, left, right):
    if left < right: # 递归终止条件：left=right,写成while的话会造成死循环。
        mid = paratition(li, left, right)  # 调用函数，取第一个元素排序后的索引
        # 两边递归调用，完成排序
        quick_sort(li, left, mid-1)
        quick_sort(li, mid+1, right)


Li = [5, 2, 4, 6, 1, 3]
quick_sort(Li, 0, len(Li)-1)
print(Li)

参考：
https://www.bilibili.com/video/BV1uA411N7c5?p=17