直接插入排序，折半插入排序、希尔排序

直接插入排序

#include <stdio.h>

int main() {
    int a[10], key;

    // 输入已排序的数组
    for (int i = 0; i < 9; i++) {
        scanf("%d", &a[i]);
    }

    // 输入需要插入的数字
    scanf("%d", &key);

    //直接插入排序
    int k=8;
    while(k>=0&&a[k]>key){
        a[k+1]=a[k];
        k--;
    }
    
    a[k+1]=key;
    // 输出排序后的数列
    for (int i = 0; i < 10; i++) {
        printf("%d\n", a[i]);
    }

    return 0;
}

折半插入排序

#include <stdio.h>

int main() {
    int a[10], key, mid, l;

    // 输入已排序的数组
    for (int i = 0; i < 9; i++) {
        scanf("%d", &a[i]);
    }

    // 输入需要插入的数字
    scanf("%d", &key);

    // 折半插入排序
    int low = 0, high = 8;

    while (low <= high) {
        mid = (low + high) / 2;
        if (key < a[mid]) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    // 移动元素
    for (l = 8; l >= low; --l) {
        a[l + 1] = a[l];
    }

    // 插入新元素
    a[l + 1] = key;

    // 输出排序后的数列
    for (int i = 0; i < 10; i++) {
        printf("%d\n", a[i]);
    }

    return 0;
}

希尔排序

       希尔排序是插入排序的一种改进算法，它的主要思想是通过将数组分为若干个子序列来减小逆序对的数量。这些子序列分别进行插入排序，然后逐渐减小序列的长度，最终达到整体有序的效果。

具体步骤如下：

选择增量序列： 选择一个增量序列，通常是通过一定规则递减的。在上述程序中，使用的是 n/2、n/4、...、1 的递减序列。

对每个子序列进行插入排序： 以当前增量作为步长，对数组中的每个子序列进行插入排序。这里的子序列是以当前增量为间隔的元素构成的。

逐渐缩小增量： 重复上述步骤，逐渐减小增量，直至增量为1。

#include <stdio.h>

// 希尔排序函数
void shellSort(int arr[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

int main() {
    int a[10], key;

    // 输入已排序的数组
    for (int i = 0; i < 9; i++) {
        scanf("%d", &a[i]);
    }

    // 输入需要插入的数字
    scanf("%d", &key);

    // 将新数字插入到已排序数组中
    a[9] = key;

    // 使用希尔排序对数组进行排序
    shellSort(a, 10);

    // 输出排序后的数列
    for (int i = 0; i < 10; i++) {
        printf("%d\n", a[i]);
    }

    return 0;
}