数据结构——折半插入排序-阿里云开发者社区

数据结构——折半插入排序

2022-12-02 425

版权

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

简介： 数据结构——折半插入排序

一、算法介绍

1.算法思想

折半插入排序的思想是借用了折半查找的思路，通过在已经有序的序列（默认序列第一个元素为有序序列）中利用二分查找快速定位插入位置，这样经过n-1趟插入就能完成排序，当元素较多时，折半插入排序效率更优于直接插入排序。

2.算法流程

默认序列第一个元素是已经有序序列，每次从无序序列中拿取一个元素，通过折半查找快速找到在有序序列中的插入位置，然后插入元素，经过n-1趟插入完成排序。默认排升序。

示例：

待排序序列：4，2，8，9，5，6，1，3，7

二、算法实现

1.代码实现

#include<iostream>
using namespace std;
void BinarySearch(int* arr, int size) {//折半插入排序
  for (int i = 1; i < size; i++) {//默认第一个元素为有序序列，所以从1开始循环
  if (arr[i] < arr[i - 1]) {//如果当前元素大于等于有序序列所有元素，不需要进行查找插入
    int  key = arr[i];//标记待插入元素
    int left = 0;
    int right = i - 1;
    while (left <= right) {
    int mid = (left + right) / 2;
    if (arr[mid] > key) {
      right = mid - 1;
    }
    else {
      left = mid + 1;
    }
    }
    for (int j = i - 1; j > right; j--) {//顺序后移
    arr[j + 1] = arr[j];
    }
    arr[right + 1] = key;//插入元素
  }
  }
}
void PrintArr(int* arr, int size) {//数组打印
  cout << endl;
  for (int i = 0; i < size; i++) {
  cout << arr[i] << ' ';
  }
}
void Test() {
  int arr[] = { 4,2,8,9,5,6,1,3,7 };
  //int arr[] = { 15,1,1,45,12,125,15,45,20,-3 };
  int size = sizeof(arr) / sizeof(arr[0]);
  cout << "排序前：";
  PrintArr(arr, size);
  BinarySearch(arr, size);
  cout << endl << "排序后：";
  PrintArr(arr, size);
}
int main() {
  Test();
  return 0;
}