'''
快速排序
复杂度 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)