用c语言写一个折半排序插入代码

折半排序插入（Binary Insertion Sort）是一种简单的查找算法，它结合了折半查找和插入排序的思想。这个过程通常用于构建一个已排序的序列，新元素将按照升序插入到正确的位置。下面是用C语言编写的一个基本折半插入排序的示例：

#include <stdio.h>

// 折半查找函数
int binary_search(int arr[], int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            low = mid + 1;
        else
            high = mid - 1;
    }
    // 如果没找到目标，返回比目标大一的位置，因为我们要插入
    return low;
}

// 折半插入排序函数
void binary_insertion_sort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int index = binary_search(arr, i, key);

        // 将key从i开始向右移动
        while (index > 0 && arr[index - 1] > key) {
            arr[index] = arr[index - 1];
            index--;
        }
        arr[index] = key;
    }
}

// 测试函数
void print_array(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

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

    printf("Original array:\n");
    print_array(arr, n);
    
    binary_insertion_sort(arr, n);

    printf("Sorted array using Binary Insertion Sort:\n");
    print_array(arr, n);

    return 0;
}

在这个例子中，`binary_search`函数用于查找适当位置，然后`binary_insertion_sort`函数通过不断调整元素顺序来插入新元素。运行上述程序，你会看到原始数组和经过折半插入排序后的有序数组。