【算法】希尔排序、计数排序、桶排序、基数排序

本文主要是介绍【算法】希尔排序、计数排序、桶排序、基数排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1 希尔排序
2 计数排序
3 桶排序
4 基数排序

1 希尔排序

"""
希尔排序（Shell Sort）是一种插入排序算法的改进版本，得名于其发明者Donald Shell。
它通过比较一定间隔的元素来进行排序，以减少数据移动的次数，从而提高排序效率。
希尔排序的核心思想是：将待排序的数组按照一定的间隔分组，对每组元素进行插入排序，
然后逐渐缩小间隔，直到间隔为1时对整个数组进行一次插入排序。
这样可以保证在最后一次排序时，数据基本接近有序，从而减少了插入排序的比较和移动次数。希尔排序的步骤：
1 选择间隔序列：选择一个间隔序列（例如：n/2, n/4, ..., 1，其中n是数组的长度），并按照间隔将数组元素分组。
2 分组插入排序：对每个间隔的分组进行插入排序。因为间隔较大，分组内元素较少，插入排序相对快速。
3 缩小间隔：将间隔缩小，重复步骤2。
4 最终排序：当间隔缩小到1时，整个数组的元素几乎有序，进行最后一次插入排序。希尔排序的时间复杂度：
希尔排序的时间复杂度取决于间隔序列的选择，最优情况下时间复杂度可达到 O(nlogn)，但最坏情况下可能达到 O(n2)。
通常，使用Hibbard间隔序列或Sedgewick间隔序列等更优化的间隔可以提高效率。
"""def insert_sort_gap(li: list, gap: int):for i in range(gap, len(li)):  # i表示摸到的牌的下标tmp = li[i]  # 摸到的牌j = i - gap  # j指的是手里的牌的下标while j >= 0 and li[j] > tmp:li[j + gap] = li[j]j -= gapli[j + gap] = tmpdef shell_sort(li: list):d = len(li) // 2while d >= 1:insert_sort_gap(li, d)d //= 2li = list(range(10))
import randomrandom.shuffle(li)
print("打散后的列表：", li)
shell_sort(li)
print("希尔排序后的列表：", li)运行结果：
打散后的列表： [7, 4, 5, 6, 0, 3, 2, 9, 1, 8]
希尔排序后的列表： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

2 计数排序

"""
计数排序（Counting Sort）是一种线性时间的非比较排序算法，适用于对一定范围内的整数进行排序。
它通过计数数组来统计每个元素的出现次数，并根据计数来确定元素在排序后数组中的位置。
计数排序特别适用于范围不大的整数集合，且在需要稳定排序的情况下表现良好。计数排序的基本步骤：
1 确定范围：找出待排序数组中的最大值和最小值，确定计数数组的大小。
2 初始化计数数组：创建一个大小为“最大值减最小值加1”的计数数组，并将其初始化为0。
3 计数元素：遍历原数组，将每个元素出现的次数记录在计数数组相应的位置。
4 累加计数：将计数数组中的计数值进行累加，从而得到每个元素在排序后数组中的正确位置。
5 生成排序数组：根据计数数组中的信息，将元素放入最终的排序数组中。计数排序的特点：
1 时间复杂度：计数排序的时间复杂度为 O(n+k)，其中 n 是待排序数组的大小，k 是计数数组的大小（即范围）。
2 空间复杂度：需要额外的 O(k) 空间来存储计数数组，因此在元素范围较大时空间复杂度较高。
3 稳定性：计数排序是稳定的排序算法，即在排序后相等元素的相对顺序保持不变。计数排序的应用场景：
计数排序非常适合用来排序整数集合，尤其当数值范围相对较小（例如考试成绩、年龄等）的情况下。
在处理某些特定的计数问题时，计数排序也可以扩展用于统计出现频率等。"""
import time
import random
import copydef cal_time(func):def wrapper(*args, **kwargs):t1 = time.time()result = func(*args, **kwargs)t2 = time.time()print("%s running time: %s secs." % (func.__name__, t2 - t1))return resultreturn wrapper@cal_time
def count_sort(li: list, max_count=100):# 创建一个计数数组，大小为 max_count + 1，初始值全部为0# 这个数组用来记录每个值在原列表中出现的次数count = [0 for _ in range(max_count + 1)]# 遍历原列表li，对每个元素进行计数# 具体做法是将对应元素的值作为索引，在计数数组中增加其出现次数for val in li:count[val] += 1# 清空原列表li，因为我们将按排序顺序重新填充这个列表li.clear()# 枚举计数数组，index是数组的索引，对应原列表中的值；val是该值出现的次数for index, val in enumerate(count):# 如果某个值出现了多次（val>0），就将这个值添加回原列表中val次for _ in range(val):li.append(index)# li = [random.randint(1, 100) for _ in range(1000)]
# print(li)
# count_sort(li)
# print(li)@cal_time
def sys_sort(li: list):li.sort()# 比较时间复杂度
li = [random.randint(1, 100) for _ in range(10000000)]
li1 = copy.deepcopy(li)
li2 = copy.deepcopy(li)
count_sort(li1)
sys_sort(li2)

3 桶排序

"""
桶排序（Bucket Sort）是一种基于分布的排序算法，适用于均匀分布的数列。
它通过将元素分配到不同的桶（子区间）中，再对每个桶内的元素进行排序，最后将所有桶中的元素合并得到有序序列。
桶排序通常用于处理数据分布均匀且取值范围有限的场景。桶排序的基本步骤：
1 创建桶：根据待排序数组的元素值范围，创建一定数量的桶。
2 分配元素到桶：将每个元素放入对应的桶中。通常使用简单的映射函数，如将元素值除以桶的区间长度，决定该元素进入哪个桶。
3 对每个桶内部进行排序：由于每个桶内的元素数量通常较少，常用插入排序、快速排序等对桶内元素排序。
4 合并桶中的元素：将各个桶中的元素按顺序合并，得到最终的有序数组。桶排序的特点：
1 时间复杂度：在理想情况下，桶排序的时间复杂度为O(n+k), n是待排序的元素数量，k是桶的数量。最坏情况下时间复杂度为 O(n2k)（当所有元素都分配到同一个桶时）。
2 空间复杂度：空间复杂度主要由桶的数量和元素数量决定，通常为 O(nk)。
3 稳定性：桶排序是稳定的排序算法。桶排序的应用场景：桶排序特别适用于对均匀分布的数据进行排序。常见的应用包括排序浮点数、考试成绩分段统计等。它在处理数据量大且分布较均匀的情况下具有较好的性能。
"""
import randomdef bucket_sort(li: list, n=100, max_num=10000) -> list:"""桶排序代码演示:param li: 传入的列表:param n: 桶的数量:param max_num: 表示待排序数组中可能出现的最大值:return: 排序好的列表"""# 创建n个空桶，每个桶是一个空列表，用来存放分配到该桶的元素buckets = [[] for _ in range(n)]# 遍历待排序的列表li，将每个元素放入相应的桶中for val in li:# 计算当前元素val应放入的桶的索引i# val // (max_num // n) 计算出元素应该放入的桶位置# 使用min确保索引不会超过最后一个桶的索引i = min(val // (max_num // n), n - 1)# 将元素val放入计算出的桶buckets[i]中buckets[i].append(val)# 保持桶内的顺序，通过直接插入排序的方式，插入时保持桶内元素有序# 对新插入的元素进行插入排序，确保桶内元素有序。这个循环从新加入的元素位置开始，向前检查并保持桶内元素顺序。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)  # 将每个桶中的元素按顺序加入到 sorted_li 中，最终得到排序后的列表# 返回排序后的列表return sorted_lili = [random.randint(0, 100) for _ in range(1000000)]
print(li)
li = bucket_sort(li)
print(li)

4 基数排序

"""
基数排序（Radix Sort）是一种非比较型的整数排序算法，它将整数按位数分割，然后按每个位数依次进行排序。
基数排序的核心思想是利用桶排序或计数排序来对数字的每一位（个位、十位、百位等）进行排序，从最低位开始，逐步构建出最终的有序数组。基数排序的步骤：
1 确定最大位数：找到数组中最大数的位数，决定排序的轮数。
2 按位排序：从最低位（个位）开始，对每一位使用稳定的排序算法（如计数排序）进行排序。
3 逐位递进：对下一位（十位、百位等）重复上述过程，直到最高位排序完成。基数排序的特点：
1 时间复杂度：假设待排序的 n 个整数的最大位数为 d，每个位上的数的范围为 k，则基数排序的时间复杂度为 O(d(n+k))。
2 空间复杂度：需要额外的空间来存放临时数组和桶，空间复杂度为 O(n+k)。
3 稳定性：基数排序是稳定的排序算法。基数排序的实现：基数排序有两种常见的实现方式：LSD（Least Significant Digit） 和 MSD（Most Significant Digit）。1 LSD 从最低位开始排序。2 MSD 从最高位开始排序。
"""
import randomdef radix_sort(li: list):# 找到列表中的最大数，以确定排序时需要处理的最大位数max_num = max(li)# it 代表当前处理的是哪一位，从个位（it=0）开始it = 0# 当 10 的 it 次方小于等于 max_num 时，继续循环处理下一位while 10 ** it <= max_num:# 创建 10 个空桶，每个桶是一个列表，用来存放对应数字的元素buckets = [[] for _ in range(10)]# 遍历原始列表中的每个元素for val in li:# 计算当前位（it 位）的数字，如个位、十位、百位等digit = (val // 10 ** it) % 10# 根据当前位的数字，将元素放入对应的桶中buckets[digit].append(val)# 清空原始列表，以便将桶中的数据重新写回li.clear()# 依次将所有桶中的数据按顺序重新合并回原始列表for buc in buckets:li.extend(buc)# 增加 it，以便处理下一位（从个位到十位，十位到百位）it += 1li = list(range(10))
random.shuffle(li)
print(li)
radix_sort(li)
print(li)