折半插入排序01例子折半插入的基本思想(图)

半插入排序

01

例子

减半插入的基本思想：将数组划分为有序部分和待排序部分，每次从待排序序列中依次选择一个元素，找到待排序的正确位置通过对半搜索，从有序序列部分中对元素进行排序。插入。

与直接插入排序相比，折叠插入排序的优点是减少了关键字比较的次数，但是插入待排序元素所需的元素移动次数并没有优化，时间复杂度仍然是O(n2)@ >。

“哨兵”位也用在半插入中，即数组下标为0的位置，用于临时存放要排列的元素。算法如下：

●将要排序的元素i复制到A[0]：A[0].key = A[i].key

● low 指向有序序列的第一个位置，high 指向有序序列的最后一个位置：low=1，high=i-1

● mid=(low+high)/2，比较A[0]和A[mid]的大小。如果A[0].key >A[mid].key堆排序算法时间复杂度，则表示A[0]插入A[mid~high]，此时low=mid+1；如果A[0].key，表示A[0]要插入A[low~mid]，设high=mid-1。

● high 时，搜索结束堆排序算法时间复杂度，待排序元素的插入位置为 high+1。

我们使用数组作为栗子（栗子不使用“哨兵”，temp是要排队的元素）：

第一回合：

第一个元素3直接被认为是有序的，所以要排序的元素从第二个元素1开始，即temp=1。从图中可以看出mid指向值3，temp，high=high-1=0-1=-1，此时high循环结束，1的插入位置high+1=0 .

第二轮：

待排队元素：7.low=0，high=1，计算后mid=0指向值1。temp>mid，此时low=mid+1=1。

再次计算mid=(1+1)/2=1，指向值3，temp>mid，此时low=mid+1=2，low>high，循环结束，插入位置温度高+1 = 2。

第三轮：

要排队的元素 5。如下图，mid第一次指向值3，temp>mid，此时low=mid+1=2。

再次计算mid=2，指向值7、5

后两个元素的排序过程就不详细展示了，大家应该明白吧！

02

代码

03

总结

代码毕竟是代码，与算法有数十亿的差异。有一些小细节需要注意！

● 待排列的元素从第二个元素开始（下标为2），即最外层循环的初值为2，i=2

● 一定要记得将要排队的元素分配给哨兵A[0]，以免移动时覆盖后面的元素

交流群

咨询微信

强哥

荣妈妈

微博

▲ @Strong Connectivity 计算机考研

小程序

电脑刷机小程序