10.2 插入排序

01直接插入排序

1、直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。

02 其他插入排序

1、折半插入排序：由于插入排序的基本操作是在一个有序表中进行查找和插入，这个”查找“操作可利用”折半查找“来实现，由此进行的插入排序称之为折半插入排序。

2、2-路插入排序：是在折半插入排序的基础上再改进之，其目的是减少排序过程中移动记录的次数，但为此需要n个记录的辅助空间。

3、表插入排序：表插入排序的结果只是求得一个有序链表。

03希尔排序

1、希尔排序（Shell’s Sort）又称”缩小增量排序“，它也是一种属插入排序类的方法，但在时间效率上较前述几种排序方法有较大的改进。

2、希尔排序的特点是：子序列的构成不是简单地”逐段分割“，而是将相隔某个”增量“的记录组成一个子序列。

C语言 | 输出斐波那契前30列​ mp.weixin.qq.com

文章来源: zhuanlan.zhihu.com，作者：小林C语言，版权归原作者所有，如需转载，请联系作者。

原文链接：zhuanlan.zhihu.com/p/338802663