折半插入排序 c语言

折半插入排序是一种插入排序算法，它通过减少比较次数来提高排序效率。下面是C语言的折半插入排序代码：

#include <stdio.h>

void binaryInsertionSort(int arr[], int n) {
    int i, j, left, right, mid, key;
    for (i = 1; i < n; ++i) {
        key = arr[i];
        left = 0;
        right = i - 1;
        while (left <= right) {
            mid = (left + right) / 2;
            if (arr[mid] > key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        for (j = i - 1; j >= left; --j) {
            arr[j + 1] = arr[j];
        }
        arr[left] = key;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    int arr[n];
    int i;
    for (i = 0; i < n; ++i) {
        scanf("%d", &arr[i]);
    }
    binaryInsertionSort(arr, n);
    for (i = 0; i < n; ++i) {
        printf("%d ", arr[i]);
    }
    return 0;
}