折半插入排序算法解析

一、理解算法思想

每次从原有数据中取出一个数，插入到之前已经排好的序列中，直到所有的数全部取完，该算法过程与直接插入排序算法极为相似，区别就是在插入的时候 高效 的选择位置。

使用二分（折半）查找来选择插入位置

二、算法流程

外层循环用来找到序列中无序的入口

进入无序入口后，记录入口位置元素值并进入二分查找

二分查找结束后，将元素值向依次后覆盖

最后将入口位置的元素值插入到二分查找结束的位置即可

三、代码实现

1、源代码

int main(void)
{
  int arr[6] = { 27,45,50,35,66,32 };
  int len = sizeof(arr) / sizeof(arr[0]);
  cout << "排序前：" << endl;
  for (int i = 0; i < len; i++) {
  cout << arr[i] << " ";
  }
  cout << endl;
  for (int i = 1; i < len ; i++)
  {
  if (arr[i] < arr[i - 1])
  {
    int temp = arr[i]; 
    int low = 0;
    int high = i - 1;  
    while (low <= high) {
    int middle = (low + high) / 2;
    if (temp < arr[middle])
    {
      high = middle - 1;
    }
    else
    {
      low = middle + 1;
    }
    }
    for (int j = i - 1; j >= high + 1; j--)
    {
    arr[j + 1] = arr[j];
    }
    arr[high + 1] = temp;
  }
  }
  cout << "排序后：" << endl;
  for (int i = 0; i < len; i++) {
  cout << arr[i] << " ";
  }
}

解析：

由于不会出现重复元素，所以最后一定会将搜索区间缩小至low与high重合(左右区间端点不断移动)。在最后一次循环时，low、high的值相同，在比较完成后，左右端点发生交错，相差为1，此时要选择一个变量的值作为新插入元素的位置参照。

需要明确的是，在左右端点重合之前，待插入元素必定是能够落在low与high的区间内的，这就决定了tmp一定大于low对应的元素，小于high对应的元素。

而且最终的插入位置应该放在最后比较元素的后一个位置，也就是mid对应位置的后面，所以是mid+1。如果用low表示，就刚好是low，如果用high表示，则是high+ 1。

2、运行效果

四、调试程序，分析算法流程

1、详细的调试过程

使用VS编译器，在程序更改序列的的位置设置断点

启动调试，可以看到程序已经运行到断点处且无错误

根据上一个调试结果可以看到第一个程序入口位置是 i = 3，二分查找结束的条件是 low >high，那么继续逐语句调试，观察数组中元素值的变化

上一张图片arr[3]变为了50，随之j--，再次调试的话arr[2]的值也会发生改变

可以看到arr[2]的值变为45，那么下一次调试将跳出for循环，arr[1]的将变为入口位置的元素值

那么该入口的折半插入排序就完成了，接下来运行到外层for循环，继续寻找无序入口并重复上面的操作

上次调试的情况是当i=5时，进入折半排序入口，流程和前五步一致，所以直接看最终调试结果

2、时间复杂度

对于折半插入排序来说，元素的串位次数没有并发生变化，只是在查找位置是更加快速了，因此该算法与直接插入排序处于同一量级。不过在数据量很大时，要优于直接插入排序，时间复杂度仍为O(n 2 n^2n

2

)