折半插入排序

待我称王封你为后i 2022-05-09 08:28 258阅读 0赞

插入的基本思想

①每次插入，都从前面的有序子表中查找出待插入元素应该被插入的位置；  
　　②给插入位置腾出空间，将待插入元素复制到表中的插入位置。  
　　注意到该算法中，总是边比较边移动元素，下面将比较和移动操作分离开来，即先折半查找出元素的待插入位置，然后再同意地移动待插入位置之后的所有元素。当排序表为顺序存储的线性表时，可以对直接插入排序算法作如下改进：由于是顺序存储的线性表，所以查找有序子表时可以用折半查找来实现。在确定出待插入位置后，就可以同意地向后移动元素了。

算法代码

void InsertSort(Elemtype A\[\],int n)\{  
int i,j,low,high,mid;  
for(i=2;i<=n;i++)\{  
A\[0\]=A\[i\];  
low=1;  
high=i-1;//设置折半查找的范围，从1到i-1,A\[0\]用来暂存元素  
while(low<=high)\{  
mid=(low+high)/2;  
if(A\[mid\].key>A\[0\].key) high=mid-1;//查找左半子表  
else low=mid+1;//查找右半子表  
\}

for(j=i-1;j>=high+1;--j)
                A[j+1]=A[j];//统一向后移动元素，空出插入位置
        A[high+1]=A[0];//插入操作
    }

\}1234567891011121314151617

实例及解析

第一趟：按上述代码的流程分析，从A\[2\]开始计算，｛11｝是一个已排序子表，按关键字13进行折半查找它的位置，代码的上半部分查找该元素元素应该插入的位置为A\[2\]，所以下半部分并不需要移动元素，已排序子表为｛11，13｝  
　　第二趟：从A\[3\]开始计算，low=1，high=2，mid=1,因为7<11，所以high=2-1=1；第二次循环mid=1,7<11,high=0,循环不满足条件，此时开始移动元素；要移动的元素范围为A\[1\]到A\[2\]，A\[1\]=7。  
　　第三趟第四趟依此类推……（只要记住一点，先折半查找元素的应该插入的位置，然后统一移动应该移动的元素，再将这个元素插入到正确的位置）

算法时间复杂度

时间复杂度：不难看出，折半插入排序仅仅是减少了比较元素的次数，约为O(nlogn)，而且该比较次数与待排序表的初始状态无关，仅取决于表中的元素个数n；而元素的移动次数没有改变，它依赖于待排序表的初始状态。因此，折半插入排序的时间复杂度仍然为O(n²)，但它的效果还是比直接插入排序要好。  
　　空间复杂度：很显然，排序只需要一个位置来暂存元素，因此空间复杂度为O（1）。

--------------------

本文来自 李正浩大魔王 的CSDN 博客 ，全文地址请点击：[https://blog.csdn.net/m0\_37316917/article/details/70990523?utm\_source=copy][https_blog.csdn.net_m0_37316917_article_details_70990523_utm_source_copy]

[https_blog.csdn.net_m0_37316917_article_details_70990523_utm_source_copy]: https://blog.csdn.net/m0_37316917/article/details/70990523?utm_source=copy