排序算法（系列）

希尔排序（Shell Sort）是一种插入排序的改进版本。它是基于插入排序的思想，通过将待排序的元素举行分组，然后对每组举行插入排序，渐渐淘汰分组的大小，最终完成排序。希尔排序的核心思想是将序列分为多个子序列，对每个子序列举行插入排序，然后渐渐缩小子序列的长度，直到最后一次对整个序列举行插入排序。
计数排序（Counting Sort）是一种非比力排序算法，它通过确定每个元素在数组中的位置来完成排序。计数排序的核心思想是统计每个元素的出现次数，并根据出现次数确定元素在排序后的最终位置。计数排序适用于待排序元素为确定范围的整数的情况。
桶排序（Bucket Sort）是一种排序算法，它将待排序的元素分别为多个桶，每个桶中存放一定范围内的元素。然后对每个桶中的元素举行排序，最后将所有桶中的元素按桶的顺序依次取出，即得到排好序的序列。桶排序适用于待排序元素分布均匀的情况。
基数排序（Radix Sort）是一种多关键字排序算法，它将待排序元素按照关键字的各个位举行排序。基数排序从最低位开始，对每个关键字举行排序，直到最高位。基数排序可以用于对十进制、二进制等各种进制的数举行排序。基数排序的核心思想是按照关键字的各个位举行分配和收集，通过多次分配和收集来完成排序。
这四种排序算法都有各自的特点和适用范围，可以根据具体标题的要求选择合适的排序算法。
目次

希尔排序
计数排序O(n)
桶排序
基数排序
基数排序
基数排序的实现

---

希尔排序

基于插入排序（摸牌）（把插入排序中的1换成了gap)

1. # 希尔排序
2. def insert_search_gap(li,gap):
3.    for i in range(gap,len(li)):      # i 表示趟数，也表示未排序的数的下标
4.        temp = li[i]        # 用于存储将要排序的数
5.        j = i-gap     # 表示已排序好的数下标
6.        while j >= 0 and li[j] > temp:          # 找出能够插入的位置
7.            li[j+gap] = li[j]         # 向右移动 空出位置放置li[i]
8.            j -= gap              # 下标向前指 继续比较
9.        li[j+gap] = temp
10. ​
11. def shell_sort(li):
12.    d = len(li)//2
13.    while d > 0:
14.        insert_search_gap(li,d)
15.        d //= 2
16. ​
17. ​
18. li = list(range(100))
19. import random
20. random.shuffle(li)
21. print(li)
22. shell_sort(li)
23. print(li)

复制代码

计数排序O(n)

1. # 计数排序
2. def count_sort(li,max_count=100):     #max_count = 100默认最大的数是100
3.    count = [0 for _ in range(max_count+1)]
4.    for val in li:
5.        count[val] += 1
6.    li.clear()
7.    for ind,val in enumerate(count):       # ind列表下标 val下标次数
8.        for j in range(val):
9.            li.append(ind)
10. ​
11. import random
12. li = [random.randint(0,100)for _ in range(1000)]
13. print(li)
14. count_sort(li)
15. print(li)

复制代码

桶排序

时间复杂度较难讨论
适用于分布均匀且数额较大。

1. # 桶排序  不重要
2. def bucket_sort(li,n = 100,max_num = 10000):
3.    bucket = [[] for _ in range(n)]     # 创建桶
4.    for var in li:
5.        i = min(var //(max_num // n), n-1)      # i 表示var放到几号桶 若100桶，但是没有这时候就放在n-1 = 99
6.        bucket[i].append(var)
7.    # 保持桶里边的顺序
8.    for j in range(len(bucket[i])-1,0,-1):
9.        if bucket[i][j] < bucket[i][j-1]:
10.            bucket[i][j],bucket[i][j-1] = bucket[i][j-1], bucket[i][j]
11.        else:
12.            break
13.    sorted_li = []
14.    for buc in bucket:
15.        sorted_li.extend(buc)
16.    return sorted_li
17. ​
18. import random
19. ​
20. li = [random.randint(0,100)for i in range(10000)]
21. # print(li)
22. li = bucket_sort(li)
23. print(li)

复制代码

基数排序(O(kn))

基数排序

先按照个位举行桶排序（按照个位进桶再依次出来），再按照十位举行桶排序（一样）

基数排序的实现

1. # 基数排序的实现
2. # 时间复杂度O(kn)（k表示数字位数）
3. def radix_sort(li):
4.     max_num = max(li)      # 最大值9—>1次分桶,99->2,888->3,10000->5
5.     it = 0
6.     while 10 ** it <= max_num:
7.         buckets = [[] for _ in range(10)]
8.         # 分桶
9.         for var in li:
10.             # 取个位it=0，987%10=7
11.             # 取十位987 it=1  987//10->98 98%10=8
12.             # 取百位987 it=2   987//10^it=9 9%10=9
13.             digit = (var//10**it) % 10
14.             buckets[digit].append(var)
15.         li.clear()
16.         for buc in buckets:
17.             li.extend(buc)
18.         it += 1
21. import random
22. li = list(range(1000))
23. random.shuffle(li)
24. radix_sort(li)
25. print(li)

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。