快速排序，写了第三遍，终于可以不看资料一遍写好了
import sys
sys.setrecursionlimit(100000000)
def partition(li,left,right):
    temp = li[left]
    while left < right:
        while left < right and li[right] >= temp:
            right -= 1
        li[left] = li[right]
        while left < right and li[left] <= temp:
            left += 1
        li[right] = li[left]
    li[left] = temp
    return left
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)
class Solution:

    def MySort(self , arr: List[int]) -> List[int]:
        # write code here
        quick_sort(arr,0,len(arr)-1)
        return arr