完整教程：2- 十大排序算法（希尔排序、计数排序、桶排序）

2- 十大排序算法（希尔排序、计数排序、桶排序）

四、希尔排序

• 希尔排序：希尔排序的计算复杂度约为0(n的1.5次方)。当n= 10的5次方时，计算量约3000万次，远小于0(n2)的100亿次。

• {8,7,6,5,4,3,2,1}，共8个数，从小到大排序

• （1）gap=8/2=4，对间距为4的数排序。

  • 共4组数的间距为4，这四组数分别是{8,4}、{7，3}、{6,2}、{5,1}。
  • 分别在这4组数内部做插入排序
  • 经过这一轮操作，较大的数挪到了右边，更靠近它们排序后的终止位置。

• （2）gap=4/2=2，对间距为2的数排序。
  • 共有2组数的间距为2，分别是(4，2，8，6}、{3，1,7,5}。
  • 分别做插入排序，例如(4,2,8,6}做插入排序的结果是{2,4,6,8}。
  • 例:处理8时，它前面的2、4已经排好序且更小，8不用做什么操作。这就是上一轮gap=4的排序操作带来的好处。

• （3）gap=2/2=1，对间距为1的数排序
  • 由于前2轮的操作，到这一轮有很多数不用操作。
  • 例:{4,6, 8}这3个数。
  • 例:处理到{5}时，它前面已经得到{1，2,3,4,6}，那么{5}只需要插到{6}前面即可

def shell_sort(arr):
n = len(arr)
gap = n // 2 # 初始间隔，选择数组长度的一半
# 不断减少间隔，直到间隔为1
while gap >
0:
# 按照间隔分组进行插入排序
for i in range(gap, n):
key = arr[i] # 当前要插入的元素
j = i
# 在当前组内按照间隔进行插入排序
while j >= gap and arr[j - gap] > key:
arr[j] = arr[j - gap] # 把比key大的元素向右移动
j -= gap
arr[j] = key # 插入当前元素到正确的位置
gap //= 2 # 更新间隔，减半
# 输入一个数字列表
arr = list(map(int, input("请输入数字，用空格分隔：").split()))
shell_sort(arr) # 调用希尔排序函数
print("排序后的列表：", arr) # 输出排序后的列表

五、计数排序(Counting sort)

• 计数排序：计数排序的应用场景狭窄只适合“小而紧凑”的数列:所有的数值都不太大，且均匀分布

• 基于哈希思想的排序算法，它使用一个额外的数组(称为计数数组)来统计每个数出现的次数，然后基于次数，输出排序后的数组。

• 以数列a[]={5,2,7.3,4,3}为例。

• (1)找到最大值7，建计数数组cnt[8];

• (2)把数列中的每个数看成cnt[i]的下标i对应的cnt[i]计数。例如{5}对应cnt[5]=1，{2}对应cnt[2]=1，2个{3}对应cnt[3]= 2.

• 遍历cnt[]，若cnt[i]=k，输出k次i。输出结果就是排序结果。

def counting_sort(arr):
# 如果数组为空，直接返回空列表
if not arr:
return arr
# 找到数组中的最大值和最小值
max_val = max(arr)
min_val = min(arr)
# 创建计数数组，数组大小为最大值与最小值之差加1
range_of_elements = max_val - min_val + 1
count = [0] * range_of_elements
# 将每个元素的出现次数记录到计数数组中
for num in arr:
count[num - min_val] += 1
# 使用计数数组生成排序后的结果
sorted_arr = []
for i in range(range_of_elements):
sorted_arr.extend([i + min_val] * count[i]) # 生成排序后的元素，重复次数为计数数组中的值
return sorted_arr
# 输入一个数字列表
arr = list(map(int, input("请输入数字，用空格分隔：").split()))
sorted_arr = counting_sort(arr) # 调用计数排序函数
print("排序后的列表：", sorted_arr) # 输出排序后的列表

六、桶排序(Bucket sort)

• 桶排序:分治思想，分成k个桶

• (1)有k个桶，把要排序的n个数尽量均匀分到每个桶中

• (2)要求桶之间也是有序的，即第i个桶内所有的数小于第i+1个桶内所有的数;

• (3)在每个桶内部排序

• (4)最后把所有的桶合起来，就是排序的结果，

def bucket_sort(arr):
# 如果数组为空，直接返回空列表
if not arr:
return arr
# 找到数组中的最大值和最小值
max_val = max(arr)
min_val = min(arr)
# 确定桶的数量，这里我们使用元素数量的平方根作为桶的数量
bucket_count = len(arr)
# 创建桶的列表，每个桶是一个空的子列表
buckets = [[] for _ in range(bucket_count)]
# 根据元素的值，将元素放入相应的桶中
for num in arr:
# 通过缩放和移动范围，将元素映射到桶的索引
index = int((num - min_val) / (max_val - min_val + 1) * (bucket_count - 1))
buckets[index].append(num)
# 对每个桶内的元素进行排序
sorted_arr = []
for bucket in buckets:
# 使用插入排序、快速排序或其他算法排序每个桶内的元素
sorted_arr.extend(sorted(bucket)) # 这里使用内置的sorted()进行排序
return sorted_arr
# 输入一个数字列表
arr = list(map(int, input("请输入数字，用空格分隔：").split()))
sorted_arr = bucket_sort(arr) # 调用桶排序函数
print("排序后的列表：", sorted_arr) # 输出排序后的列表