计算机知识插入排序思维导图
简单介绍插入排序的内容
树图思维导图提供 计算机知识插入排序思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 计算机知识插入排序思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：7a7861ca3466e3f133e9c4596826b776
思维导图大纲
插入排序思维导图模板大纲
直接插入排序
原理
每次将一个待排记录按其关键字大小插入到前面已有序 的子序列中，直到全部排完
时间复杂度
最坏O(n²)
元素顺序与排序结果顺序相反、比较次数最大、移动次数最大
平均O(n²)
最好与最坏情况的平均值约为 n²/4
最好O(n)
前面已有序 、只需比较不需移动
空间复杂度
仅用了一个辅助空间 O(1)
适用范围
适用于基本有序、数据量不大的顺序存储和链式存储的线性表
稳定性
稳定
折半插入排序
原理
比较和移动操作分离，先折半查找要插入的位置，再统一地移动待插入位置后的所有元素
时间复杂度
平均O(n²)
与直接插入排序相比，比较次数减少了、为O(nlogn)、移动次数未改变
适用范围
顺序存储线性表
空间复杂度
仅用了一个辅助空间 O(1)
希尔排序
原理
取步长为d1，将待排序列分割成若干个“特殊”表，分别进行插入排序，再多次取d2,d3.....排序，当整个表“基本有序时”，再对全体记录进行一次直接插入排序
适用范围
仅适用于顺序存储的线性表、对于大规模的排序可以达到很高的效率
时间复杂度
数学界的难题、还没算出来、最坏O(n²)
空间复杂度
仅用了一个辅助空间 O(1)
相关思维导图模板
树图思维导图提供 计算机系统结构思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 计算机系统结构思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：d55735120bfc45f09e7d4f00035ca040
树图思维导图提供 计算机网络病毒思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 计算机网络病毒思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：6f1c8acd6ded214123c400f4dfca2fee
沪公网安备 31011502019485号
上海工商