对随机产生的1000个整数构成的序列分别进行直接插入、简单选择排序、希尔、快速、归并排序，并统计各自的比较次数。使用c语言

下面是使用C语言实现对随机产生的1000个整数构成的序列分别进行直接插入、简单选择排序、希尔、快速、归并排序，并统计各自的比较次数的代码：

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

#define MAX 1000

int insert_sort(int a[], int n);
int select_sort(int a[], int n);
int shell_sort(int a[], int n);
int quick_sort(int a[], int left, int right);
int merge_sort(int a[], int left, int right);
void merge(int a[], int left, int mid, int right);

int main()
{
    int a[MAX], b[MAX], c[MAX], d[MAX], e[MAX];
    int i, j, n;
    int count1 = 0, count2 = 0, count3 = 0, count4 = 0, count5 = 0;
    clock_t start, end;

    srand((unsigned int)time(NULL));
    for (i = 0; i < MAX; i++) {
        a[i] = rand() % MAX + 1;
        b[i] = a[i];
        c[i] = a[i];
        d[i] = a[i];
        e[i] = a[i];
    }

    start = clock();
    count1 = insert_sort(a, MAX);
    end = clock();
    printf("直接插入排序的比较次数：%d，用时：%dms\n", count1, end - start);

    start = clock();
    count2 = select_sort(b, MAX);
    end = clock();
    printf("简单选择排序的比较次数：%d，用时：%dms\n", count2, end - start);

    start = clock();
    count3 = shell_sort(c, MAX);
    end = clock();
    printf("希尔排序的比较次数：%d，用时：%dms\n", count3, end - start);

    start = clock();
    count4 = quick_sort(d, 0, MAX - 1);
    end = clock();
    printf("快速排序的比较次数：%d，用时：%dms\n", count4, end - start);

    start = clock();
    count5 = merge_sort(e, 0, MAX - 1);
    end = clock();
    printf("归并排序的比较次数：%d，用时：%dms\n", count5, end - start);

    return 0;
}

/* 直接插入排序 */
int insert_sort(int a[], int n)
{
    int i, j, temp;
    int count = 0;

    for (i = 1; i < n; i++) {
        temp = a[i];
        for (j = i - 1; j >= 0 && a[j] > temp; j--) {
            a[j + 1] = a[j];
            count++;
        }
        a[j + 1] = temp;
    }

    return count;
}

/* 简单选择排序 */
int select_sort(int a[], int n)
{
    int i, j, min, temp;
    int count = 0;

    for (i = 0; i < n - 1; i++) {
        min = i;
        for (j = i + 1; j < n; j++) {
            if (a[j] < a[min]) {
                min = j;
            }
            count++;
        }
        if (min != i) {
            temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }
    }

    return count;
}

/* 希尔排序 */
int shell_sort(int a[], int n)
{
    int i, j, gap, temp;
    int count = 0;

    for (gap = n / 2; gap > 0; gap /= 2) {
        for (i = gap; i < n; i++) {
            temp = a[i];
            for (j = i - gap; j >= 0 && a[j] > temp; j -= gap) {
                a[j + gap] = a[j];
                count++;
            }
            a[j + gap] = temp;
        }
    }

    return count;
}

/* 快速排序 */
int quick_sort(int a[], int left, int right)
{
    int i, j, pivot, temp;
    int count = 0;

    if (left < right) {
        pivot = a[left];
        i = left;
        j = right;
        while (i < j) {
            while (i < j && a[j] >= pivot) {
                j--;
                count++;
            }
            if (i < j) {
                a[i++] = a[j];
            }
            while (i < j && a[i] < pivot) {
                i++;
                count++;
            }
            if (i < j) {
                a[j--] = a[i];
            }
        }
        a[i] = pivot;
        count += quick_sort(a, left, i - 1);
        count += quick_sort(a, i + 1, right);
    }

    return count;
}

/* 归并排序 */
int merge_sort(int a[], int left, int right)
{
    int mid;
    int count = 0;

    if (left < right) {
        mid = (left + right) / 2;
        count += merge_sort(a, left, mid);
        count += merge_sort(a, mid + 1, right);
        merge(a, left, mid, right);
    }

    return count;
}

void merge(int a[], int left, int mid, int right)
{
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int *L = (int*)malloc(sizeof(int) * n1);
    int *R = (int*)malloc(sizeof(int) * n2);

    for (i = 0; i < n1; i++) {
        L[i] = a[left + i];
    }
    for (j = 0; j < n2; j++) {
        R[j] = a[mid + 1 + j];
    }

    i = j = 0;
    k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            a[k++] = L[i++];
        } else {
            a[k++] = R[j++];
        }
        count++;
    }
    while (i < n1) {
        a[k++] = L[i++];
    }
    while (j < n2) {
        a[k++] = R[j++];
    }

    free(L);
    free(R);
}

其中，insert_sort、select_sort、shell_sort、quick_sort、merge_sort 分别实现直接插入排序、简单选择排序、希尔排序、快速排序、归并排序，每个函数返回的是比较次数。main函数中使用 rand 函数产生 1000 个随机整数，然后对其进行五种排序方法的测试，最后输出比较次数以及排序用时。