排序(python实现)

 1 def partition(li,left,right):
 2     tmp = li[left]
 3     while left < right:
 4         while left<right and li[right]>=tmp: #从最右面开始找比tmp小的数
 5             right -= 1
 6         li[left] = li[right] #把右边的值写到左边空位上
 7         while left<right and li[left]<=tmp:
 8             left += 1
 9         li[right] = li[left] #把右边的值写到左边空位上
10     li[left] = tmp #把tmp归为
11     return left #这个是分成两部分的值的下标
12 
13 def quick_sort(li,left,right):
14     if left < right:    
15         mid = partition(li,left,right)
16         quick_sort(li,left,mid-1)
17         quick_sort(li,mid+1,right)

 1 def sift(li,low,high):
 2     i = low  #i最开始指向根节点
 3     j = 2*i+1 #把堆顶存起来
 4     tmp = li[low]
 5     while j<=high:#只要j位置有数
 6         if j+1 <= high and li[j+1] > li[j]: #如果右孩子有并且比较大
 7             j = j+1  #j指向右孩子
 8         if li[j] > tmp:
 9             li[i] = li[j]
10             i = j #往下看一层
11             j = 2*i+1
12         else:  #tmp更大，把tmp放到i的位置上
13             # li[i] = tmp  #把tmp放到某一级领导位置上
14             break
15     li[i] = tmp  #把tmp放到叶子节点上 此i已经2*i+1了
16 
17 def head_sort(li):
18     n = len(li)
19     for i in range((n-2)//2,-1,-1):
20         # i表示建堆的时候调整的部分的根的下标
21         sift(li,i,n-1)
22     #建堆完成了 
23     for i in range(n-1,-1,-1):
24         #i 指向当前堆的最后一个元素
25         li[0],li[i] = li[i],li[0]
26         sift(li,0,i-1)#i-1是新的high

 1 def merge(li,low,mid,high):
 2     i = low
 3     j = mid+1
 4     ltmp = []
 5     while i<=mid and j<=high: #只要左右两边都有数
 6         if li[i] < li[j]:
 7             ltmp.append(li[i])
 8             i+=1
 9         else:
10             ltmp.append(li[j])
11             j+=1
12     while i <= mid:
13         ltmp.append(li[i])
14         i+=1
15     while j <= high:
16         ltmp.append(li[j])
17         j+=1
18     li[low:high+1] = ltmp
19 
20 def merge_sort(li,low,high):
21     if low < high:
22         mid = (low+high)//2
23         merge_sort(li,low,mid)  #把左边排好序
24         merge_sort(li,mid+1,high) #把右边排好序
25         merge(li,low,mid,high)