快速排序

参考实现

'''
快速排序
复杂度 O(nlogn)
'''


def partition(list, left, right):
    # 存第一个元素
    temp = list[left]
    while left < right:
        while list[right] >= temp and left < right:  # 右边找比 temp 小的元素
            right -= 1  # 左移
        list[left] = list[right]  # 右边值放到左边空位
        while list[left] < temp and left < right:
            left += 1
        list[right] = list[left]  # 左边值放到右边空位
    list[left] = temp  # 归位
    return left

def quick_sort(list,left,right):
    if left < right:#至少两个元素
        mid = partition(list,left,right)
        quick_sort(list, left, mid - 1)
        quick_sort(list,  mid + 1,right)

nums = [5, 7, 4, 6, 3, 1, 2, 9, 8]
print(nums)
quick_sort(nums, 0, len(nums) - 1)

print(nums)