一些排序 (python实现)

►快速排序 <时间复杂度O(n㏒n)>

 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)

View Code

►堆排序 <时间复杂度O(n㏒n)> (不用递归)

 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

View Code

►归并排序 <时间复杂度O(n㏒n)>

 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)

View Code

优劣顺序：快速排序 > 归并排序 > 堆排序

其他一些low逼

►冒泡排序 <时间复杂度O(n²)>

1 def bubble_sort(li):
2     for i in range(len(li)-1):  #i=趟数
3         exchange = False
4         for j in range(len(li)-i-1):  #无序区
5             if li[j] < li[j+1]:
6                 li[j],li[j+1] = li[j+1],li[j]
7                 exchange = True
8         if not exchange:
9             return

View Code

►选择排序 <时间复杂度O(n²)> 新建列表，内存占用×2

1 def select_sort_simple(li):
2     li_new = []
3     for i in range(len(li)):
4         min_val = min(li)  
5         li_new.append(min_val)  
6         li.remove(min_val)  # O(n)操作，删除之后列表元素需要挪位
7     return li_new

View Code

►插入排序 <时间复杂度O(n²)>

1 def insert_sort(li):
2     for i in range(1,len(li)):
3         tmp = li[i]
4         j = i-1 #最后一张牌的下标
5         while j >= 0 and li[j] > tmp:
6             li[j+1] = li[j]
7             j -= 1
8         li[j+1] = tmp

View Code

►希尔排序

►计数排序 <时间复杂度O(n)>

1 def count_sort(li,max_count=100):
2     count = [0 for _ in range(max_count+1)]
3     for val in li:
4         count[val] += 1
5     li.clear()
6     for index,val in enumerate(count):
7         for i in range(val):
8             li.append(index)

View Code

►桶排序

►基数排序