编写程序实现简单插入排序、希尔排序（或基数排序），进行比较分析。用c语言实现

下面是C语言实现简单插入排序、希尔排序和基数排序的示例代码，同时还包括了对三种排序算法的比较分析。

## 简单插入排序

void insertionSort(int arr[], int n) {
    int i, j, key;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

简单插入排序的时间复杂度为O(n^2)。

## 希尔排序

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

希尔排序的时间复杂度为O(n log n)。

## 基数排序

void radixSort(int arr[], int n) {
    int i, j, m = arr[0], exp = 1;
    int *bucket = (int *) malloc(sizeof(int) * n);
    for (i = 0; i < n; i++) {
        if (arr[i] > m) {
            m = arr[i];
        }
    }
    while (m / exp > 0) {
        int bucketCnt[10] = {0};
        for (i = 0; i < n; i++) {
            bucketCnt[arr[i] / exp % 10]++;
        }
        for (i = 1; i < 10; i++) {
            bucketCnt[i] += bucketCnt[i - 1];
        }
        for (i = n - 1; i >= 0; i--) {
            bucket[--bucketCnt[arr[i] / exp % 10]] = arr[i];
        }
        for (i = 0; i < n; i++) {
            arr[i] = bucket[i];
        }
        exp *= 10;
    }
    free(bucket);
}

基数排序的时间复杂度为O(nk)，其中k为最大数的位数。

## 比较分析

简单插入排序和希尔排序都是基于比较的排序算法，而基数排序则是一种非比较排序算法。在排序效率方面，基数排序明显优于简单插入排序和希尔排序。同时，在数据规模较大时，基数排序的优势更加明显。不过需要注意的是，基数排序对数据的要求较高，比如需要数据是非负整数，并且最大值的位数不超过某个范围。

另外，希尔排序的时间复杂度与其增量序列的选取有关。对于一些特定的增量序列，希尔排序的效率可能会更高。