随机产生100 个整数构成的序列，分别以直接插入、冒泡、希尔、快速、归并等排序算法排序，并统计各自的比较次数。c语言

以下是一个示例代码，其中包括直接插入排序、冒泡排序、希尔排序、快速排序、归并排序的实现。每个算法的比较次数都被记录在对应的变量中，最后输出比较次数。

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

// 直接插入排序
int insertion_sort(int arr[], int len) {
    int i, j, tmp, cmp = 0;
    for (i = 1; i < len; i++) {
        tmp = arr[i];
        for (j = i - 1; j >= 0 && tmp < arr[j]; j--) {
            arr[j + 1] = arr[j];
            cmp++;
        }
        arr[j + 1] = tmp;
    }
    return cmp;
}

// 冒泡排序
int bubble_sort(int arr[], int len) {
    int i, j, tmp, cmp = 0;
    for (i = 0; i < len - 1; i++) {
        for (j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                cmp++;
            }
        }
    }
    return cmp;
}

// 希尔排序
int shell_sort(int arr[], int len) {
    int i, j, tmp, gap, cmp = 0;
    for (gap = len / 2; gap > 0; gap /= 2) {
        for (i = gap; i < len; i++) {
            tmp = arr[i];
            for (j = i - gap; j >= 0 && tmp < arr[j]; j -= gap) {
                arr[j + gap] = arr[j];
                cmp++;
            }
            arr[j + gap] = tmp;
        }
    }
    return cmp;
}

// 快速排序
int quick_sort(int arr[], int left, int right) {
    int i, j, pivot, tmp, cmp = 0;
    if (left < right) {
        i = left;
        j = right;
        pivot = arr[left];
        while (i < j) {
            while (i < j && arr[j] >= pivot) {
                j--;
                cmp++;
            }
            if (i < j) {
                arr[i++] = arr[j];
                cmp++;
            }
            while (i < j && arr[i] <= pivot) {
                i++;
                cmp++;
            }
            if (i < j) {
                arr[j--] = arr[i];
                cmp++;
            }
        }
        arr[i] = pivot;
        cmp++;
        cmp += quick_sort(arr, left, i - 1);
        cmp += quick_sort(arr, i + 1, right);
    }
    return cmp;
}

// 归并排序
int merge(int arr[], int left, int mid, int right) {
    int i, j, k, cmp = 0;
    int *tmp = (int *)malloc((right - left + 1) * sizeof(int));
    i = left;
    j = mid + 1;
    k = 0;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            tmp[k++] = arr[i++];
            cmp++;
        } else {
            tmp[k++] = arr[j++];
            cmp++;
        }
    }
    while (i <= mid) {
        tmp[k++] = arr[i++];
    }
    while (j <= right) {
        tmp[k++] = arr[j++];
    }
    for (i = left, k = 0; i <= right; i++, k++) {
        arr[i] = tmp[k];
    }
    free(tmp);
    return cmp;
}

int merge_sort(int arr[], int left, int right) {
    int mid, cmp = 0;
    if (left < right) {
        mid = (left + right) / 2;
        cmp += merge_sort(arr, left, mid);
        cmp += merge_sort(arr, mid + 1, right);
        cmp += merge(arr, left, mid, right);
    }
    return cmp;
}

int main() {
    int arr[100];
    int i, cmp;
    srand(time(NULL));
    printf("原序列：\n");
    for (i = 0; i < 100; i++) {
        arr[i] = rand() % 1000;
        printf("%d ", arr[i]);
    }
    printf("\n");
    cmp = insertion_sort(arr, 100);
    printf("直接插入排序后的序列：\n");
    for (i = 0; i < 100; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n比较次数：%d\n", cmp);
    cmp = bubble_sort(arr, 100);
    printf("冒泡排序后的序列：\n");
    for (i = 0; i < 100; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n比较次数：%d\n", cmp);
    cmp = shell_sort(arr, 100);
    printf("希尔排序后的序列：\n");
    for (i = 0; i < 100; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n比较次数：%d\n", cmp);
    cmp = quick_sort(arr, 0, 99);
    printf("快速排序后的序列：\n");
    for (i = 0; i < 100; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n比较次数：%d\n", cmp);
    cmp = merge_sort(arr, 0, 99);
    printf("归并排序后的序列：\n");
    for (i = 0; i < 100; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n比较次数：%d\n", cmp);
    return 0;
}