折半插入排序c++

折半插入排序是一种插入排序算法的变种，它通过使用二分查找来寻找插入位置，从而提高了插入的效率。下面是一个使用C++实现的折半插入排序的示例代码：

#include <iostream>
using namespace std;

void binaryInsertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        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 >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = key;
    }
}

int main() {
    int arr[] = {5, 2, 8, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    binaryInsertionSort(arr, n);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

这段代码实现了折半插入排序算法，将数组按升序排序。首先，我们从第二个元素开始遍历数组，将当前元素作为待插入元素。然后，使用二分查找在已排序区间中找到合适的插入位置。最后，将待插入元素插入到正确的位置，并将已排序区间中的元素后移。重复这个过程，直到遍历完所有元素，得到一个有序数组。