10.2 插入排序

01

直接插入排序

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

02

其他插入排序

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

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

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

03

希尔排序

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

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

如果您觉得本篇文章对您有作用，请转发给更多的人，点一下好看就是对小编的最大支持！