用调试来帮你分析并拿捏折半插入排序算法的流程

2023-06-27 73

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 用调试来帮你分析并拿捏折半插入排序算法的流程

折半插入排序算法解析

一、理解算法思想

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

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

二、算法流程

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

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

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

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

三、代码实现

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] << " ";
  }
}