插入排序的基本思想是：将无序序列中的一个或几个记录“插入”到有序序列（开始时为空）中，从而增加记录的有序序列的长度。本节介绍两种插入排序：直接插入排序（straight insertion sort）和希尔排序（Shell’s sort）。

1.直接插入排序

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

【1】输入元素序列：45，62，35，77，92，55，14，35，按从小到大的序列排序。

初始关键字：i=1  {45}  62  35  77  92  55  14  35

            i=2  {45  62}  35  77  92  55  14  35

            i=3  {35  45  62}  77  92  55  14  35

            i=4  {35  45  62  77}  92  55  14  35

            i=5  {35  45  62  77  92}  55  14  35

            i=6  {35  45  55  62  77  92}  14  35

            i=7  {14  35  45  55  62  77  92}  35

            i=8  {14  35  35  45  55  62  77  92}

【效率分析】对于直接插入排序：

直接插入排序的空间效率：仅用了一个辅助单元。

    直接插入排序的时间复杂度为O(n*n)。

    直接插入排序是稳定的排序方法。

直接插入排序算法简便，比较适用于待排序记录数目较少且基本有序的情况。当待排记录数目较大时，直接插入排序的性能不是很好。

当记录数量n很大时，则比较次数将大大增加，对于有序表，为了减少关键字的比较次数，可采用折半插入排序。其基本思想是：用折半查找法在有序表中找到正确的插入位置，然后移动记录，空出插入位置，再进行插入。时间复杂度仍为O(n*n)，且也为稳定排序方法。

2.希尔排序

希尔排序又称“缩小增量排序”，是1959年由D.L.Shell提出来的，也是一种插入排序的方法，但在时间上较直接插入排序方法有较大的改进。

直接插入排序算法简单，在n值较小时，效率比较高，在n值很大时，若序列按关键码基本有序，效率依然较高，其时间效率可提高到O(n)。希尔排序即是从这两点出发，给出插入排序的改进方法。

希尔排序的具体做法为：将记录序列分成若干子序列，分别对每个子序列进行插入排序。例如，将 n 个记录分成 d 个子序列：

{ R[1]，R[1+d]，R[1+2d]，…，R[1+kd] }

{ R[2]，R[2+d]，R[2+2d]，…，R[2+kd] }

    …

{ R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d] }

其中，d 称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为 1。 

【效率分析】对于希尔排序：

希尔排序的时间复杂度为O(n*n)，若待排记录序列为正序时，为O(n)。

希尔排序是不稳定的排序方法。

希尔排序的分析是一个复杂的问题，因为它的时间耗费是所取的增量序列的函数，到目前为止，尚未有人求得一种最好的增量序列。