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)
领取专属 10元无门槛券
私享最新 技术干货