面试题：C++插入排序的优化实现

#include <iostream>
#include <vector>

// 使用二分查找确定插入位置
int binarySearch(const std::vector<int>& arr, int target, int left, int right) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid + 1;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return left;
}

// 优化后的插入排序
void insertionSortOptimized(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;
        int insertIndex = binarySearch(arr, key, 0, j);
        while (j >= insertIndex) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;
    }
}

int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6};
    std::cout << "Original array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    insertionSortOptimized(arr);

    std::cout << "Sorted array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

优化思路

二分查找确定插入位置：
- 对于传统插入排序，在将一个数据插入到已经排好序的数组中的适当位置时，需要逐个比较元素以确定插入位置。在优化版本中，使用二分查找来找到插入位置。
- binarySearch函数实现了二分查找逻辑。它接收数组、目标值、左边界和右边界作为参数。在函数内部，通过比较中间元素与目标值，不断缩小查找范围，最终返回目标值应插入的位置。
移动元素：
- 找到插入位置后，传统插入排序需要从插入位置开始逐个向后移动元素，以腾出空间插入当前元素。在优化后的代码中，同样是从插入位置开始向后移动元素，但是由于通过二分查找确定了插入位置，减少了比较次数。
- 在insertionSortOptimized函数中，先使用二分查找找到当前元素key的插入位置insertIndex，然后从j（当前元素前一个位置）开始，将大于key的元素向后移动，直到j小于insertIndex，最后将key插入到合适位置。这样在确定插入位置时，利用二分查找减少了比较次数，从而优化了插入排序的性能。

星途面试题库

面试题：C++插入排序的优化实现

知识考点

面试题答案

优化思路