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

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)