学习日记

**
学习知识点

插入排序

        插入排序的基本思路是每次插入一个元素，每一趟完成对一个待排元素的放置，直到全部插入完成。

折半插入排序

        由于在插入排序的过程中，已经生成了一个(排好的元素组成的）有序数列。所以在插入待排元素时可以使用折半查找Q的方式更快速的确定新元素的位置，当元素个数较多时，折半插入排序优于直接插入排序。

算法说明

        每次从原有数据中取出一个数，插入到之前已经排好的序列中，直到所有的数全部取完，那么新的有序排列也就完成了。这个过程与直接插入排序十分类似，不同的地方在于插入时如何寻找位置。

        其优势在于利用已排好的元素有序的特点，使用折半查找的方式快速确定位置。

复杂度
        折半查找只是减少了比较次数，但是元素的移动次数不变。折半插入排序平均时间复杂度为O(n^2)；空间复杂度为O(1)；是稳定的排序算法。

 

算法流程

1.输入数据集被分为有序区和无序区两部分。

2.最初有序区没有元素，从无序区不断取出元素放入，保证放入的元素均已有序。

3.已知前i个元素已排好（下标从0至i-1)，从无序区取出第一个元素(数据集的第i+1个元素)。

4.先与有序区的最后一个元素比较如果较大则代表该元素已经在合适的位置，则直接归入有序区，进入下一个元素的判断。如果较小则需要进—步确定位置，执行以下步骤。

5.搜索区间为从low至high，初始区间为整个有序区(从0至i-1) 。

6.将待插入元素记录在临时变量tmp中，为后续的元素串位做准备。

7.计算mid = (low + high)/ 2，将该位置的元素与R[i]比较。

8.不断的缩小搜索区间，直到确定插入位置(原理与折半查找相同)。

9.确定位置后，将有序区中的元素从后至前逐个后串，最后将tmp中的值覆盖到插入位置。