人生没有彩排，每天都是现场直播，不仅收视率低，而且工资不高。

  插入排序根据查找插入位置的方式不同可以分为三类：按顺序法查找插入位置的——直接插入排序；按折半法也叫二分法查找插入位置的——折半插入排序;缩小增量多遍插入排序的——希尔排序。本文探讨有关折半插入排序的知识。

思想：   借助二分查找的思想，先查找插入位置，再移动数据，最后插入到正确的位置。   我们都知道直接插入排序是一个边比较边移动的过程，而折半插入排序是先确定插入的位置，再来进行移动。   插入排序的效率是由比较的次数和移动的次数共同决定的，而折半插入排序就是通过降低比较的次数来提高排序的效率。一起看看是如何进行操作的。

操作图解分析：   有一组数据如下，现在我们需要将这组数据按从小到大进行排序。   将这一组数据分为有序组（有颜色的）和无序组（没有颜色的），数据的第一个元素默认为有序，如下：   将无序组中1号位置的数据进行拷贝，同时将1号位置收编到有序组序列中。此处将被拷贝位置的数据进行抹去方便进行分析，如下：   接着采用折半查找在有序组中查找插入位置，低地址端为有序组的第一个位置（记为：low），高地址端为有序组的最后一个有效元素的位置（记为：high）,中端地址为mid=（low+high）/2，如下：   将94和mid所指位置上的元素进行比较，发现94>81,则low=mid+1，如下：

  当high小于low时，则low所指的位置即为插入位置，low所指的位置即1号位置此时并没有有效数据则不需要进行移动，直接进行插入，如下：

  继续从无序中将2号位置的数据进行拷贝，同时将二号位置收编到有序组的序列，依旧抹去2号位置的数据如下：   high指向有序组最后一个有效数据的位置，low指向有序组的第一个位置，mid为两者和的二分之一，如下：   将11和mid所指位置的元素进行比较，11 temp = array[i];//拷贝数据 high = i - 1;//指向有序组中最后一个有效数据 low = 0;//指向有序组中第一个数据位置 while (low low = mid + 1;//指向比较位置的后一个位置 } else//说明插入位置在mid的左边 { high = mid - 1;//指向比较位置的前一个位置 } } for (j = i; j >=low; j--)//将查找的位置元素及其后面的元素整体移动一个位置 { array[j] = array[j - 1]; } array[low] = temp;//插入到正确位置 } } 五.总结

  折半插入排序通过减少元素比较次数使得排序效率得到提高。由于二分查找比顺序查找快，所以折半插入排序的平均性能来说比直接插入排序要好。   时间复杂度为O（n^2），空间复杂度为O（1），是一种稳定的插入排序

如何提高插入排序的效率：  减少元素的比较次数  减少元素的移动次数

  下期我们讲解通过减少元素的比较次数和移动次数来提高插入排序效率的——希尔排序。

  我是老胡，感谢阅读！！❤️ ❤️