当前位置: 首页 > news >正文

完整教程:2- 十大排序算法(希尔排序、计数排序、桶排序)

完整教程:2- 十大排序算法(希尔排序、计数排序、桶排序)

2- 十大排序算法(希尔排序、计数排序、桶排序)

四、希尔排序

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

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) # 输出排序后的列表
http://www.hskmm.com/?act=detail&tid=36777

相关文章:

  • 分词器模型
  • 2025 年国内品牌设计公司最新推荐排行榜:聚焦行业领军者优势,精选优质服务商深度解析
  • 报考PostgreSQL中级认证证书多少钱?
  • 2025 年 LFT 材料源头厂家最新推荐权威榜单:复合 / 注塑 / 增强 / 轻量化 / 长碳纤 / 长玻纤 / 耐高温 LFT 材料优质公司推荐
  • Windows Server 2025 安装IIS服务
  • 易路薪酬能力深度解析:以科技赋能企业薪酬管理新范式
  • LaTeX 项目结构优化:从基础到专业
  • Java的优势有哪些
  • 传感类语音提示器语音播报芯片最佳适配方案WT2003H
  • 集合中的贡献法
  • 广州治疗青少年心理医院口碑榜:TOP3医疗机构专业实力深度解析
  • 人狗大战Ⅱ
  • 【IEEE出版、往届会后3个月检索】2025 第九届控制工程与先进算法国际论坛(IWCEAA 2025)
  • 整装定制家具生产厂家口碑榜:TOP3企业智能制造实力深度解析
  • 实用指南:阿里云安装Docker
  • 高性能超低功耗蓝牙电子价签方案 OM6626 NRF52832
  • 软工第三次作业-结对项目
  • 给大家分享三个特别好用的在线工具,可以为你的工作节省很多时间
  • 2025 年振动筛源头厂家最新推荐榜单:权威甄选实验 / 防爆 / 精细筛分设备,揭秘靠谱供应企业
  • 2025 年最新推荐摇摆筛厂家榜单:聚焦实力雄厚供货稳定品牌,助力企业精准选购筛分设备方形/圆形/石英砂/砂石/精细摇摆筛厂家推荐
  • 1111111111
  • 2025 年中国校服厂家最新推荐榜单权威发布!深度解析优质品牌核心竞争力与选择指南
  • 【IEEE出版 | EI检索稳定】第五届IEEE能源工程与电力系统国际学术会议(IEEE-EEPS 2025)
  • 2025年丝杆升降机厂家最新行业推荐:联动丝杆升降机/螺旋丝杆升降机/蜗杆丝杆升降机/蜗轮丝杆升降机/三家兼顾工艺与适配性的实力厂家推荐
  • 2025 年同步带厂家推荐:深入剖析浙江三星胶带有限公司,探寻橡胶带行业的优质之选
  • 茶桌茶台生产厂家口碑榜:TOP3企业综合实力全景解析
  • 2025年知名的工业铝型材深加工加工厂
  • Apache Tika严重XXE漏洞分析与修复方案
  • 防火密封胶条生产厂家口碑榜:基于技术实力、客户服务及市场反馈的专业评估
  • SAP ALV小数位去除