折半插入排序的c语言完整代码

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

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

该算法的思路是：将待排序的序列分为两部分，前一部分已经有序，后一部分无序。每次将后一部分的第一个元素插入到前一部分中正确的位置，使得前一部分仍然有序。具体实现时，使用二分查找来确定插入位置，从而减少比较操作的次数。

该算法的时间复杂度为O(n^2)，但比一般的插入排序效率更高，特别是对于大规模的数据排序。