一、希尔排序
shell_sort
def insert_sort_gap(li,gap):
for i in range(gap,len(li)):
tem = li[i] # 要插入的数
j = i-gap # j指的是手里的牌的下标
while li[j] > tem and j>=0:
li[j+gap] = li[j]
j -= gap
li[j+gap] = tem def shell_sort(li):
d = len(li)//2
while d>=1:
insert_sort_gap(li,d)
d//=2
import random
li = list(range(1000))
random.shuffle(li)
shell_sort(li)
print(li,'最后结果')
计数排序
计数排序、基数排序、桶排序则属于非比较排序，算法时间复杂度O(n)，优于比较排序。但是也有弊端，会多占用一些空间，相当于是用空间换时间。
计数排序的基本思想是：对每一个输入的元素a[i]，确定小于 a[i] 的元素个数。所以可以直接把 a[i] 放到它输出数组中的位置上。
假设有5个数小于 a[i]，所以 a[i] 应该放在数组的第6个位置上。
def count_sort(li,max_count=100):
count = [0 for _ in range(max_count+1)]
# 100个
print(count)
# val取值为(0,100),1000次
for val in li:
# 遇到相同的下角标就加一
count[val] +=1 li.clear()
# 列表 clear() 方法用于清空列表，类似于 del a[:]
# 比如 count[2]=5，就有5个2的意思[2，2，2，2，2]
for ind,val in enumerate(count):
for i in range(val):
li.append(ind)
import random
# 有1000个数范围在(0,100)之间
li = [random.randint(0,100) for i in range(1000)]
print(li)
count_sort(li)
print(li)
桶排序
----------------------------
桶排序的基本思想是：把数组a划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并。桶排序要求数据的分布必须均匀，不然可能会失效。
计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。
import random def bucket_sort(li, n=100, max_num=10000):
buckets = [[] for _ in range(n)] # 创建桶
for var in li:
i = min(var // (max_num // n), n-1) # i 表示var放到几号桶里
buckets[i].append(var) # 把var加到桶里边
# 保持桶内的顺序
for j in range(len(buckets[i])-1, 0, -1):
if buckets[i][j] < buckets[i][j-1]:
buckets[i][j], buckets[i][j-1] = buckets[i][j-1], buckets[i][j]
else:
break
sorted_li = []
for buc in buckets:
sorted_li.extend(buc)
return sorted_li li = [random.randint(0,10000) for i in range(100000)]
# print(li)
li = bucket_sort(li)
print(li)
基数排序
