数据结构与算法之插入排序

有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序。

插入排序有两种：

• 直接插入排序
• 折半插入排序

直接插入排序

对于每个未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。其过程大概是这样的：

• 第一个元素就认为是有序的
• 取第二个元素，判断是否大于第一个元素。若是大于，表示已经有序，不用移动，否则将已经有序的序列整体向后移动一个位置
• 依此类推，直到所有元素已经有序。

时间复杂度

需要到两层循环来处理，外层循环用于跑多少趟，而内层循环用于移动元素位置，因此时间复杂度仍为 O ( n2 )

C语言实现

折半插入排序

从第二个元素开始逐个置入监视哨，使用low、high标签进行折半判断比较大小，并确认插入位置，该位置到最后一个数全部后移一位，然后腾出该位置，把监视哨里面的数置入该位置。依此类推进行排序，直到最后一个数比较完毕。

时间复杂度

折半插入排序, 即查找插入点的位置, 可以使用折半查找，这样可以减少比较的次数, 但是移动的次数不变，因此，时间复杂度仍为 O(n2) ;

C语言实现

对于折半插入排序算法，它需要一个哨兵，数组的0号位置是用作哨兵，而不存储数据。为什么所找到的位置是high+1呢？因为最后退出while循环一定是high = mid – 1之后，导致条件low > high而退出。所以，最后所找到的位置一定是high = mid – 1，由于减了1，所以应该插入的位置是high + 1。