目录Python全系列 教程
3567个小节阅读：5930.4k
目录
鸿蒙应用开发
C语言快速入门
JAVA全系列 教程
面向对象的程序设计语言
Python全系列 教程
Python3.x版本，未来主流的版本
人工智能 教程
顺势而为，AI创新未来
大厂算法 教程
算法，程序员自我提升必经之路
C++ 教程
一门通用计算机编程语言
微服务 教程
目前业界流行的框架组合
web前端全系列 教程
通向WEB技术世界的钥匙
大数据全系列 教程
站在云端操控万千数据
AIGC全能工具班
A A
White Night
希尔排序（Shell Sort）是一种改进的插入排序算法，它是非稳定的原地排序算法。
希尔排序的主要思想是将整个待排序的序列分割成若干子序列，对每个子序列进行插入排序，最终合并这些子序列
选择增量序列： 首先选择一个增量序列，这个序列的选择对希尔排序的性能影响很大。常用的增量序列有希尔增量（n/2,n/4,…,…,1）
按增量分组： 将待排序的序列按照增量分成若干子序列，每个子序列相对独立
对每个子序列进行插入排序： 对每个子序列使用插入排序算法进行排序
逐步缩小增量： 不断缩小增量，重复上述步骤，直到增量为1
最后一次插入排序： 当增量为1时，整个序列成为一个序列，进行最后一次插入排序
xxxxxxxxxxdef shell_sort(arr): # 获取列表的长度 n = len(arr) # 获取间隔 gap = n//2 # 循环到不能分割 while gap > 0: # 排序 # 插入排序，认为第一个数据就是已经排序好的 for i in range(gap,n): # 记录下来要比较的数据 tmp = arr[i] # 记录位置 j = i # 判断是否要做插入排序，j>=gap判断是否还数据要比较，arr[j-gap] > tmp判断是否满足插入排序条件 while j >= gap and arr[j-gap] > tmp: arr[j] = arr[j-gap] j -= gap arr[j] = tmp gap = gap // 2时间复杂度 $ O(n^2) $：希尔排序的时间复杂度与增量序列的选择有关。在最坏情况下，时间复杂度为$ O(n^2) $。最好的情况是$ O(n) $
空间复杂度 $ O(1) $、原地排序：希尔排序只需要常数级别的额外空间来存储增量和临时变量
不稳定排序：希尔排序是一种不稳定的排序算法，即相等元素的相对顺序在排序过程中可能发生变化
实时效果反馈
1. 关于希尔排序算法，说法正确的是？
A 希尔排序需要反复比较相邻的元素
B 希尔排序每一轮都是俩俩比较元素
C 希尔排序是要插入排序做为辅助排序
D 希尔排序分组数据没有特别严格规则
答案
1=>D