# 快速排序
# 将元素放到自己应有的位置，左边的数都比它小，右边的数都比它大
# 递归完成
'''
    时间复杂度，O(n*log(n)) (一般情况)
    快速排序的问题
        最坏情况   排一个倒叙的列表  解决方法，在列表中随机找一个数与第一个数进行交换
        递归  容易超过递归的最大深度


'''
import random
# import sys
# sys.setrecursionlimit(10000)   该表最大递归深度
'''
    快速排序
    快速排序思路
        取一个元素p（第一个元素），使元素p归位
        列表被p分为两个部分，左变都比p小右边都比pda
        递归完成排序
'''

def partition(li, left, right):
    # 将最左边的元素给tmp
    tmp = li[left]
    while left < right:
        while left < right and li[right]>=tmp:  # 从右面找出比tmp小的数
            right -= 1
        li[left] = li[right]    # 将右边第一个小于tmp的数放到左边的空位上
        while left < right and li[left] <= tmp:   # 从左边找出比tmp大的数
            left += 1
        li[right] = li[left]   # 将左边第一个大于tmp的数放到右边刚才腾出来的空位上
    li[left] = tmp       # 将tmp归位，放到了左边全比它小，右面全比它大的位置，也就是它最后应在的位置
    return left      # 这个left代表的就是tmp位置的索引


def quick_sort(li, left, right):
    if left < right:  # 至少有两个元素,是判断递归是否停止的条件
        mid = partition(li, left, right)
        quick_sort(li,left, mid-1)
        quick_sort(li, mid+1,right)


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