21天打卡挑战 - 经典算法之折半插入排序

​​CSDN打卡活动产出
​

活动地址：CSDN21天学习挑战赛

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。各位小伙伴，如果您：
想系统/深入学习某技术知识点…
一个人摸索学习很难坚持，想组团高效学习…
想写博客但无从下手，急需写作干货注入能量…
热爱写作，愿意让自己成为更好的人…

**

创作计划

**
机缘

实战项目中的经验分享
日常学习过程中的记录
通过文章进行技术交流
…

收获

希望以此结交到志同道合的朋友

提升自己的基础算法水平
…

日常

平均每周产出2-3篇文章

有限的精力下，只能少一些玩游戏的时间，陪女朋友的时间不敢少

憧憬

期待粉丝上万 浏览过百万！！

**

学习计划

**
学习目标

永远充满热情，坚持21天学习打卡

学习内容

经典算法之折半插入排序

学习日记

**
学习知识点

插入排序

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

折半插入排序

        由于在插入排序的过程中，已经生成了一个(排好的元素组成的）有序数列。所以在插入待排元素时可以使用折半查找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中的值覆盖到插入位置。