内容简介：插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序它的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止联想打扑克牌时理顺手中牌的时候，你从左往右依次检查你的牌，并将其和前面的牌进行比较，然后将其插入正确的位置
插入 排序 的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序
它的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止
联想打扑克牌时理顺手中牌的时候，你从左往右依次检查你的牌，并将其和前面的牌进行比较，然后将其插入正确的位置
理解起来，比 《快速排序》 容易多了
算法
- 设置监视哨r[0]，将待插入记录的值赋值给r[0]；
- 设置开始查找的位置j；
- 在数组中进行搜索，搜索中将第j个记录后移，直至r[0].key≥r[j].key为止；
- 将r[0]插入r[j+1]的位置上。
演示
也可以通过动画更清晰了解整个排序过程
动画： http://www.zhuxingsheng.com/tools/sort/sort.html
实现
插入排序包括：直接插入排序，二分插入排序（又称折半插入排序），链表插入排序，希尔排序（又称缩小增量排序）
static void insertSort1(int []sorts) {
for(int i = 1;i<sorts.length;i++) {
int tmp = sorts[i];//哨兵
int j= i-1;
while(j >=0 && tmp < sorts[j]) {
sorts[j+1] = sorts[j];//比tmp大的全部往右移动
j--;
}
//别的移完位置，把哨兵放到正确的位置
sorts[++j] = tmp;
}
}
复杂度
当问题规模为n时
最好情况（原本就是有序的）
比较次数：Cmin=n-1
移动次数：Mmin=0
最差情况（逆序）
比较次数：Cmax=2+3+4+……+n=(n+2)n/2
移动次数：Mmax=1+2+3+……+n-1=n*n/2
| Best | Average | Worst | Memory | Stable |
|---|---|---|---|---|
| n | n^2 | n^2 | 1 | Yes |
以上所述就是小编给大家介绍的《算法渣-排序-插入》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！
猜你喜欢:
- 【一起学习排序算法】4 插入排序
- 画解算法：35. 搜索插入位置
- 【数据结构与算法】—— 插入排序
- 数组排序并插入值算法（JavaScript）
- 程序兵法：插入排序算法 Java 源版
- 【译】Swift算法俱乐部-插入排序
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
产品经理手册（原书第4版）（白金版）
[美] 琳达·哥乔斯(Linda Gorchels) / 祝亚雄、冯华丽、金骆彬 / 机械工业出版社 / 2017-8 / 65.00
产品经理的职责起点是新产品开发，贯穿产品生命周期的全过程。本书按上下游产品管理进行组织。 在上游的新产品开发流程中，作者阐述了如何从市场、产品、行业、公司的角度规划企划方案，并获得老板、销售部、运营部的资源支持，推进新产品的项目流程，实现所有目标，制定和实施新产品发布。 下游产品的管理核心在于生命周期的管理，营销更是生命周期管理的重中之重。产品经理如何让产品满足客户需求，让客户获得对产......一起来看看 《产品经理手册（原书第4版）（白金版）》 这本书的介绍吧!
