插入排序——折半插入排序

2023-12-13 20:17:36

1、简述:

折半插入排序(binary insertion sort)是对插入排序算法的一种改进,由于排序算法过程中,就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列,这样我们不用按顺序依次寻找插入点,可以采用折半查找的方法来加快寻找插入点的速度。

实现步骤:

  • 定义:已知列表arr,从第二个元素开始,i=1,arr[temp] = arr[i], arr[low] 表示首元素,arr[high]表示末元素,中间值arr[mid] = arr[ (low+high)/2];
  • 比较temp和mid 的元素大小,
    • 当temp < mid,则选择low到mid-1的位置作为新插入区域,即[low, high=mid-1];
    • 否则,选择mid+1到high的位置作为新插入区域,即[low=mid+1, high];
    • 循环直到low<=high不成立
  • 移动元素:将[low, i)位置的元素向后移动,把temp的元素插到low的位置。

2、复杂度

时间复杂度:O(n2)(比直接插入算法明显减少了关键字之间比较的次数,因此速度比直接插入排序算法快,但记录移动的次数没有变)

空间复杂度:O(1)

3、稳定性:稳定排序

4、例子

C++代码:?

#include <iostream>
using namespace std;

#define LEN 8 // 有LEN个元素要排

void BInsertSort(int arr[], int length)
{
    for(int i = 1; i < length; i++){
              
        int temp = arr[i];
        int low = 0;
        int high = i - 1;
      
        while(low <= high){  // 在arr[low..high]中折半查找有序插入的位置
            int mid = (low + high) / 2;   // 折半
            if(temp < arr[mid]){ // 关键字相同时,使low = m + 1,到高半区,保证稳定性
                high = mid - 1; // 插入点在低半区
            }else{
                low = mid + 1; // 插入点在高半区
            }
        }
      
        for(int j = i; j >= low + 1; j--){
            arr[j] = arr[j - 1];
        }
      
        arr[low] = temp;
        cout<<"i="<<i<<"的排序结果:";
        for (int a = 0;a < length;a++) {
            cout << arr[a] << " ";
        }
        cout<<endl;
    }
}
int main(void)
{
    int arr[LEN] = {45, 98, 66, 90, 88, 78, 25, 45};
    BInsertSort(arr, 8);
    return 0;
}

输出结果:

i=1的排序结果:45 98 66 90 88 78 25 45 
i=2的排序结果:45 66 98 90 88 78 25 45 
i=3的排序结果:45 66 90 98 88 78 25 45 
i=4的排序结果:45 66 88 90 98 78 25 45 
i=5的排序结果:45 66 78 88 90 98 25 45 
i=6的排序结果:25 45 66 78 88 90 98 45 
i=7的排序结果:25 45 45 66 78 88 90 98 

?参考:折半插入排序_百度百科

文章来源:https://blog.csdn.net/Ashimar_a/article/details/134978990
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。