首页 > 代码库 > 插入排序
插入排序
基本思想：每次将一个待排序的记录，按其关键字大小插入已经排好序的文件中的适当位置，直到全部记录插入完为止（像打牌一样，边抓边整理）
直接插入排序
1.算法思想
假设待排序的记录存放在数组R[1....n]中。初始时，i=1，R[1]自成一个有序区，无序区为R[2...n]。然后，从i=2起直至i=n，依次将R[i]插入当前的有序区R[1...i-1]中，最后，生成含n个记录的有序区。
2.算法分析
（1）O(n) =< 时间复杂度 =< O(n^2)
（2）辅助空间复杂度S(n) = O(1),是一个就地排序
（3）直接插入排序是稳定的排序方法
希尔排序
1.算法思想
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取得增量dt=1(dt<dt-1<...<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法，是对直接插入排序法的改进。
2.算法分析
（1）增量序列的选择
【1】最后一个增量必须为1。
【2】应该尽量避免序列中的值（尤其是相邻的值）互为倍数的情况。（若互为倍数相当于执行多了一趟同等增量排序）
（2）希尔排序的时间性能优于直接插入排序，时间复杂度对比：O( n^(1+a) ) < O( n^2 )[ 0<a<1]
【1】当文件初态基本有序时直接插入排序所需的比较和移动次数均较少
【2】当n值较小时，n和n^2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度O(n^2)差别不大
【3】在希尔排序开始时增量较大，分组较多，每组的记录数少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数 目逐渐增多，但由于已经以d(i-1)作为距离排过序，使文件较接近于有序状态，所有新的一趟排序过程也较快。
（3）希尔排序是不稳定的排序方法
（4）辅助空间复杂度S(n) = O(1)，是一个就地排序
哨兵
一切为简化边界条件而引入的附加结点（元素）均可称为哨兵。
作用：
1.保存数据的副本，防止丢失数据
2.防止判定条件越界
来自为知笔记(Wiz)
插入排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。