快速排序算法

temp = [3 ,7 ,2 ,9 ,1 ,4 ,6 ,8 ,10 ,5]

# 快排算法
def quickSort(arr, left=None, right=None):
    # 初次传入数组时的判断，也可以直接传入，用于直接初始化
    left = 0 if not left else left
    right = len(arr) -1 if not right else right

    # 当left的index小于right的才能继续，否则就返回了，也就是完成了这一部分的排序
    if left < right:
        
        # 对这个区间的内容进行排序，并返回一个中间值的index
        # 并不是真的排序，只是将大值和小值以中间值为分割变成两个区间
        position = get_postition(arr, left, right)
        # 左边再次进行快排
        quickSort(arr, left, position - 1)
        # 右边再次进行快排
        quickSort(arr, position+1, right)
    

# 将区间的第一个值作为区间的中间值，
# 将这个区间分为更小的两个区间，以这个中间值，
# 吧这个中间值放到区间的中间，并将返回中间值的index，
# 然后作为下一次的排序子区间
def get_postition(arr, left, right):
    # 以第一个值作为中间值
    middle = left
    index = middle + 1
    i = index

    while i <= right:
        # 比中间值小，放在左边，然后移动指针
        # 和中间值一样就两个指针都向前移动，
        # 比中间值大，index不变，i指针向前移动，知道找到比中间值小的再进行交换
        if arr[i] < arr[middle]:
            swap(arr, i, index)
            index += 1
        i += 1

    # 当前的index是在大区间值上，index-1在小区间的最后一个值上
    # 将中间值移动到这个区间的中间
    swap(arr, middle, index-1)
    # 经过交换，小值，middle， 大值，index-1就是middle所在位置
    return index-1

# 交换的封装
def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

quickSort(temp)
print(temp)