经典排序算法——折半插入排序

15

折半插入排序

①基本思想

②演示

③算法代码

④性能

折半插入排序(Binary Insert Sort)是对插入排序算法的一种改进,由于在排序的过程中,就是不断的依次将元素插入到已经排好的序列中;由于前半部分为已经排好的数列,所以我们不需要按顺序依次寻求插入点,可以采用折半查找的思想加快寻找插入点的速度。

以数组a[8]=为例,以下仅展示前几次的排序思想

从第二个数据5开始向前插入,low=high=mid=0,a[mid]=8>temp,则high=mid-1=-1,插入点为a[high+1]=a[0]的位置,8后移一位

a[mid]>temp,high=mid-1=-1,插入点为a[high+1]=a[0]的位置,8和5向后移动一位

a[mid]>temp,high=mid-1=0,如下图

a[mid]

a[mid]

a[mid]

a[mid]>temp,high=mid-1=2,插入点为a[high+1]=a[3]的位置,8向后移动一位

按照这种排序思想可将后面的数据依次进行排序,从而得到一个有序的数组

C++代码

Python代码

Java代码

折半插入排序是一种稳定的排序算法,时间复杂度为O(N2),空间复杂度为O(1)

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180820G0AMBZ00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注腾讯云开发者

领取腾讯云代金券