插入排序

插入排序的思想

相关算法

直接插入排序

对于待排序元素，一边和前面一个元素「比较大小」，一边「向前移动」。

空间复杂度：，时间复杂度：，算法是稳定的。

适用性：对于顺序存储和链式存储的线性表都可以。

注：当序列基本有序时，直接插入排序的性能最好。

折半插入排序

相比于直接插入排序，这种算法将「比较」和「移动」分离，比较的时候用了「折半查找」的方法。

空间复杂度：，时间复杂度：（主要在移动耗时），算法是稳定的（移动的时候可以确保稳定性）。

适用性：只适用于顺序存储的线性表。

希尔排序

在不同的步长上进行插入排序。

步长的选择：，，最后一趟的步长为
注：步长选择多上，就将序列分为多少个子序列。

空间复杂度：，时间复杂度无法算出，最坏为 ，算法是不稳定的。

适用性：只适用于顺序存储的线性表。

注：由于「直接插入排序」在基本有序时表现较好，因此希尔排序的「组内排序方法」使用的是直接插入排序。