当前位置：首页 > article >正文

数据结构之折半插入排序概念、折半插入排序的具体步骤、折半插入排序的具体代码示例

article 2024/9/25 19:23:22

折半插入排序概念

折半插入排序是一种排序算法，它是对直接插入排序的改进。在折半插入排序中，使用二分查找法来减少比较元素的次数，从而加快排序速度。具体来说，就是先将要插入的元素与已排序序列的中间元素进行比较，根据比较结果决定是向左还是向右继续查找插入位置，直到找到合适的位置为止。

折半插入排序的具体步骤

折半插入排序的具体步骤如下：

1、初始化：将数组分为已排序和未排序两部分，通常已排序部分初始时只包含数组的第一个元素，未排序部分包含其余元素。

2、循环遍历：从未排序部分的第一个元素开始，依次取出元素，记为key，进行排序。

3、二分查找插入位置：

（1）设置两个指针low和high，分别指向已排序部分的起始位置和末尾位置。
（2）进入循环，当low <= high时执行以下操作：
1.计算中间位置mid = (low + high) / 2。
2.比较key与arr[mid]的大小：
1》如果key < arr[mid]，说明插入点应在左半部分，将high更新为mid - 1。
2》否则，说明插入点应在右半部分或就是mid本身，将low更新为mid + 1。
3.重复上述过程，直到找到key的插入位置。
4、元素后移：将插入位置及其右侧的所有元素向后移动一位，为key腾出空间。

5、插入元素：将key插入到找到的插入位置。

6、重复：对未排序部分的下一个元素重复步骤2至5，直到所有元素都排序完成。

折半插入排序通过二分查找减少了比较元素的次数，但元素移动的次数与直接插入排序相同，因此时间复杂度仍为O(n^2)，但在某些情况下，特别是当输入数组部分有序时，其性能会比直接插入排序更好。

折半插入排序的具体代码示例

#include <stdio.h>

// 折半插入排序函数
void BinaryInsertSort(int arr[], int n) {
    int i, j, low, high, mid, temp;
    for (i = 1; i < n; i++) {
        temp = arr[i]; // 取出未排序部分的第一个元素
        low = 0;
        high = i - 1;
        // 使用二分查找找到插入位置
        while (low <= high) {
            mid = (low + high) / 2;
            if (temp < arr[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        // 将插入位置及其右侧的所有元素向后移动一位
        for (j = i - 1; j >= low; j--) {
            arr[j + 1] = arr[j];
        }
        // 插入元素
        arr[low] = temp;
    }
}

int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    BinaryInsertSort(arr, n); // 调用折半插入排序函数
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]); // 打印排序后的数组
    }
    return 0;
}