写一个c语言插入排序

以下是两种C语言实现插入排序的例子：

1. 使用二分查找的插入排序：

void BinInsertSort(int *a, int len) {
    int i, j;
    int left, right, mid;
    
    for (i = 2; i < len; i++) {
        if (a[i] < a[i-1]) {
            a[0] = a[i];
            left = 1;
            right = i - 1;
            
            // 查找要插入的位置
            while (left <= right) {
                mid = (left + right) / 2;
                if (a[0] < a[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            
            // 将前面比这个数大的数后移
            for (j = i - 1; j > right; j--) {
                a[j+1] = a[j];
            }
            
            a[j+1] = a[0];
        }
    }
}

2. 使用哨兵的插入排序：

// 时间复杂度：最好(O(n)) 最坏(O(n^2)) 平均(O(n^2))
// 空间复杂度: 借助哨兵(O(1))
void insert_sort(int *a, int len) {
    int i, j;
    
    for (i = 2; i < len; i++) {
        // 如果这个数比前一个数小，就要交换
        if (a[i] < a[i-1]) {
            // 把小的数存放在a[0]位置，作为哨兵
            a[0] = a[i];
            
            // 将前面比这个数大的数后移
            for (j = i - 1; a[0] < a[j]; j--) {
                a[j+1] = a[j];
            }
            
            a[j+1] = a[0];
        }
    }
}