C++折半插入排序详解以及代码实现

2023-12-26 06:13:02

1. 介绍

折半插入排序(Binary Insertion Sort)是直接插入排序的一种改进版本,主要区别在于寻找插入位置的方式。在直接插入排序中,我们使用线性搜索来找到新元素应该插入的位置,而在折半插入排序中,我们使用二分搜索来加快查找速度。

以下是折半插入排序的详细步骤:

  1. 从第一个元素开始,该元素可以认为已经被排序。
  2. 取出下一个元素,将其与已排序序列中间的元素进行比较。
  3. 如果中间元素大于新元素,说明新元素应该插入到中间元素的左侧;否则,新元素应该插入到中间元素的右侧。
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置。
  5. 将新元素插入到该位置后。
  6. 重复步骤2~5,直到所有元素都已排序。

折半插入排序的时间复杂度与直接插入排序相同,都是O(n^2)。但折半插入排序在某些情况下可以略微提高效率,因为它减少了线性搜索的时间。然而,由于折半插入排序仍然是一种比较简单的排序算法,因此在处理大规模数据时可能不够高效。

2. 代码实现

#include <iostream>  
using namespace std;  
  
// 折半插入排序函数  
void binaryInsertionSort(int arr[], int n) {  
    for (int i = 1; i < n; i++) { // 从第二个元素开始遍历数组  
        int key = arr[i]; // 保存当前元素的值  
        int low = 0, high = i - 1; // 二分搜索的初始范围  
        while (low <= high) { // 进行二分搜索  
            int mid = low + (high - low) / 2; // 计算中间位置  
            if (arr[mid] > key) { // 如果中间元素大于新元素  
                high = mid - 1; // 在左侧继续搜索  
            } else {  
                low = mid + 1; // 在右侧继续搜索  
            }  
        }  
        for (int j = i - 1; j >= low; j--) { // 将已排序元素向后移动  
            arr[j + 1] = arr[j];  
        }  
        arr[low] = key; // 将当前元素插入到已排序序列中的正确位置  
    }  
}  
  
// 测试代码  
int main() {  
    int arr[] = {5, 2, 4, 6, 1, 3}; // 待排序数组  
    int n = sizeof(arr) / sizeof(arr[0]); // 数组长度  
    binaryInsertionSort(arr, n); // 对数组进行折半插入排序  
    for (int i = 0; i < n; i++) { // 输出排序后的数组元素  
        cout << arr[i] << " ";  
    }  
    cout << endl;  
    return 0;  
}

代码总结:
折半插入排序是直接插入排序的一种改进版本,通过使用二分搜索来加快查找插入位置的速度。在实现上,折半插入排序仍然采用就地排序,不需要额外的存储空间。时间复杂度与直接插入排序相同,都是O(n^2)。然而,由于折半插入排序在某些情况下可以略微提高效率,因此在处理小规模数据时可能具有更好的性能。但需要注意的是,折半插入排序仍然是一种比较简单的排序算法,因此在处理大规模数据时可能不够高效。

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