算法--快排

import random


# 归位函数三要素: 基准值；分割；基准值归位
def partition(lst, low, high):
    pivot = lst[low]  # 基准值

    while low < high:
        while low < high and lst[high] >= pivot:
            high -= 1
        lst[low] = lst[high]

        while low < high and lst[low] <= pivot:
            low += 1
        lst[high] = lst[low]

    lst[low] = pivot  # 基准值归位
    return low


# 快速排序的两个关键点：归位，递归
def quick_sort(lst, low, high):
    if low < high:  # 至少有两个元素，才能进行递归
        mid = partition(lst, low, high)  # 找到归位的位置
        quick_sort(lst, low, mid - 1)
        quick_sort(lst, mid + 1, high)


li = list(range(100))
random.shuffle(li)
print(li)
quick_sort(li, 0, len(li) - 1)
print(li)