插入排序思维脑图思维导图
排序，直接插入排序，希尔排序等内容分解
树图思维导图提供 插入排序思维脑图 在线思维导图免费制作，点击“编辑”按钮，可对 插入排序思维脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：3a1dd455b77c4171c103e51e49544fad
思维导图大纲
插入排序思维导图模板大纲
排序
将各元素按关键字递增 or 递减重新排列
评价指标
时空复杂度
稳定性
关键字相同的元素排序后相对顺序是否改变
分类
内部排序
外部排序
数据太多无法都放入内存
特殊
任意n个关键字排序的比较次数至少为⌈log(n!)⌉次
直接插入排序
思想
每次将待排序记录按关键字大小插入已排好序序列中
代码
会写，背！
性能分析
空间复杂度O(1)
时间复杂度
最好：本来有序，n-1趟，每趟比1次，O(n)
最坏：本来逆序，共比n(n-1)/2次，O(n^2)
KCN = n(n-1)/2，总比较次数
RMN = ∑(i+2)=(n+4)(n-1)/2，总移动次数
平均：O(n^2)
稳定
适用于顺序表、链表
所有适用于链表的，时间复杂度 = 顺序表
优化：折半插入排序
折半查找找到应插入位置，只适用于顺序表，不适用于链表
为了保持稳定，A[mid] == A[0]时low = mid + 1
只改进了比较次数O(nlogn)，未改进移动次数，平均时间复杂度 = O(n^2)
希尔排序
思想
先将待排序表分割成若干子表L[i，i+d，i+2d……]，对各子表直接插入排序；缩小增量d直至d = 1
例子
子表分割是L[A[i]，A[i+d]，……]
代码
看看得了
性能分析
空间复杂度O(1)
时间复杂度
d = 1时退化为直接插入排序，否则优于
不稳定
只能用于顺序表
相关思维导图模板
树图思维导图提供 1107文家市玉萍思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 1107文家市玉萍思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：ed943ef641f6dc874860eb6095857ed6
树图思维导图提供 种子思维脑图 在线思维导图免费制作，点击“编辑”按钮，可对 种子思维脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：86f8307a40ea24607c6c79354e09377f
沪公网安备 31011502019485号
上海工商