def partition(li,left,right):

     tmp = li[left]

     while left < right:

         while left<right and li[right]>=tmp: #从最右面开始找比tmp小的数

             right -= 1

         li[left] = li[right] #把右边的值写到左边空位上

         while left<right and li[left]<=tmp:

             left += 1

         li[right] = li[left] #把右边的值写到左边空位上

     li[left] = tmp #把tmp归为

     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)

 def sift(li,low,high):

     i = low  #i最开始指向根节点

     j = 2*i+1 #把堆顶存起来

     tmp = li[low]

     while j<=high:#只要j位置有数

         if j+1 <= high and li[j+1] > li[j]: #如果右孩子有并且比较大

             j = j+1  #j指向右孩子

         if li[j] > tmp:

             li[i] = li[j]

             i = j #往下看一层

             j = 2*i+1

         else:  #tmp更大，把tmp放到i的位置上

             # li[i] = tmp  #把tmp放到某一级领导位置上

             break

     li[i] = tmp  #把tmp放到叶子节点上 此i已经2*i+1了

 def head_sort(li):

     n = len(li)

     for i in range((n-2)//2,-1,-1):

         # i表示建堆的时候调整的部分的根的下标

         sift(li,i,n-1)

     #建堆完成了

     for i in range(n-1,-1,-1):

         #i 指向当前堆的最后一个元素

         li[0],li[i] = li[i],li[0]

         sift(li,0,i-1)#i-1是新的high

 def merge(li,low,mid,high):

     i = low

     j = mid+1

     ltmp = []

     while i<=mid and j<=high: #只要左右两边都有数

         if li[i] < li[j]:

             ltmp.append(li[i])

             i+=1

         else:

             ltmp.append(li[j])

             j+=1

     while i <= mid:

         ltmp.append(li[i])

         i+=1

     while j <= high:

         ltmp.append(li[j])

         j+=1

     li[low:high+1] = ltmp

 def merge_sort(li,low,high):

     if low < high:

         mid = (low+high)//2

         merge_sort(li,low,mid)  #把左边排好序

         merge_sort(li,mid+1,high) #把右边排好序

         merge(li,low,mid,high)

 def bubble_sort(li):

     for i in range(len(li)-1):  #i=趟数

         exchange = False

         for j in range(len(li)-i-1):  #无序区

             if li[j] < li[j+1]:

                 li[j],li[j+1] = li[j+1],li[j]

                 exchange = True

         if not exchange:

             return 

 def select_sort_simple(li):

     li_new = []

     for i in range(len(li)):

         min_val = min(li)

         li_new.append(min_val)

         li.remove(min_val)  # O(n)操作，删除之后列表元素需要挪位

     return li_new

 def insert_sort(li):

     for i in range(1,len(li)):

         tmp = li[i]

         j = i-1 #最后一张牌的下标

         while j >= 0 and li[j] > tmp:

             li[j+1] = li[j]

             j -= 1

         li[j+1] = tmp

 def count_sort(li,max_count=100):

     count = [0 for _ in range(max_count+1)]

     for val in li:

         count[val] += 1

     li.clear()

     for index,val in enumerate(count):

         for i in range(val):

             li.append(index)