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

以下是C语言实现简单插入排序和希尔排序的代码：

#include <stdio.h>

// 简单插入排序
void insertionSort(int arr[], int n) {
    int i, j, temp;
    for (i = 1; i < n; i++) {
        temp = arr[i];
        for (j = i; j > 0 && arr[j-1] > temp; j--) {
            arr[j] = arr[j-1];
        }
        arr[j] = temp;
    }
}

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

int main() {
    int arr1[] = {5, 2, 7, 1, 3, 6, 4};
    int arr2[] = {5, 2, 7, 1, 3, 6, 4};
    int n = sizeof(arr1) / sizeof(arr1[0]);

    insertionSort(arr1, n);
    printf("简单插入排序结果：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr1[i]);
    }

    shellSort(arr2, n);
    printf("\n希尔排序结果：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr2[i]);
    }
    return 0;
}

我们可以通过比较简单插入排序和希尔排序的运行时间来分析它们的效率。可以使用time.h头文件中的clock()函数来计算程序执行的时间。

下面是对比简单插入排序和希尔排序的运行时间的代码：

#include <stdio.h>
#include <time.h>

// 简单插入排序
void insertionSort(int arr[], int n) {
    int i, j, temp;
    for (i = 1; i < n; i++) {
        temp = arr[i];
        for (j = i; j > 0 && arr[j-1] > temp; j--) {
            arr[j] = arr[j-1];
        }
        arr[j] = temp;
    }
}

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

int main() {
    int arr1[10000];
    int arr2[10000];
    int n = sizeof(arr1) / sizeof(arr1[0]);

    // 生成随机数组
    srand(time(NULL));
    for (int i = 0; i < n; i++) {
        arr1[i] = rand();
        arr2[i] = arr1[i];
    }

    // 计算简单插入排序的运行时间
    clock_t start1 = clock();
    insertionSort(arr1, n);
    clock_t end1 = clock();
    double time1 = (double)(end1 - start1) / CLOCKS_PER_SEC;
    printf("简单插入排序运行时间：%f秒\n", time1);

    // 计算希尔排序的运行时间
    clock_t start2 = clock();
    shellSort(arr2, n);
    clock_t end2 = clock();
    double time2 = (double)(end2 - start2) / CLOCKS_PER_SEC;
    printf("希尔排序运行时间：%f秒\n", time2);
    return 0;
}

通过运行不同大小的随机数组，可以得到希尔排序的运行时间明显优于简单插入排序。这是因为希尔排序使用了增量将数组分成多个子序列，对每个子序列进行插入排序，使得每个子序列都基本有序，然后再对整个数组进行插入排序。这样可以减少插入排序的次数，提高排序的效率。