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

下面是使用C语言编写的排序算法以及比较次数的统计：

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

// 直接插入排序
int InsertionSort(int a[], int n)
{
    int i, j, k, cnt = 0;
    for (i = 1; i < n; i++)
    {
        k = a[i];
        for (j = i - 1; j >= 0 && a[j] > k; j--)
        {
            a[j + 1] = a[j];
            cnt++;
        }
        a[j + 1] = k;
    }
    return cnt;
}

// 冒泡排序
int BubbleSort(int a[], int n)
{
    int i, j, flag = 1, cnt = 0;
    for (i = 0; i < n - 1 && flag; i++)
    {
        flag = 0;
        for (j = n - 2; j >= i; j--)
        {
            if (a[j] > a[j + 1])
            {
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
                flag = 1;
                cnt++;
            }
        }
    }
    return cnt;
}

// 希尔排序
int ShellSort(int a[], int n)
{
    int i, j, k, gap, cnt = 0;
    for (gap = n / 2; gap > 0; gap /= 2)
    {
        for (i = gap; i < n; i++)
        {
            k = a[i];
            for (j = i - gap; j >= 0 && a[j] > k; j -= gap)
            {
                a[j + gap] = a[j];
                cnt++;
            }
            a[j + gap] = k;
        }
    }
    return cnt;
}

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

// 归并排序
int Merge(int a[], int tmp[], int left, int mid, int right)
{
    int i, j, k, cnt = 0;
    i = left;
    j = mid + 1;
    k = left;
    while (i <= mid && j <= right)
    {
        if (a[i] <= a[j])
            tmp[k++] = a[i++];
        else
        {
            tmp[k++] = a[j++];
            cnt += mid - i + 1;
        }
    }
    while (i <= mid)
        tmp[k++] = a[i++];
    while (j <= right)
        tmp[k++] = a[j++];
    for (i = left; i <= right; i++)
        a[i] = tmp[i];
    return cnt;
}

int MergeSort(int a[], int tmp[], int left, int right)
{
    int mid, cnt = 0;
    if (left < right)
    {
        mid = (left + right) / 2;
        cnt += MergeSort(a, tmp, left, mid);
        cnt += MergeSort(a, tmp, mid + 1, right);
        cnt += Merge(a, tmp, left, mid, right);
    }
    return cnt;
}

int main()
{
    int a[300], tmp[300], i, cnt;
    srand(time(NULL));
    for (i = 0; i < 300; i++)
        a[i] = rand() % 1000;
    cnt = InsertionSort(a, 300);
    printf("InsertionSort: %d\n", cnt);
    cnt = BubbleSort(a, 300);
    printf("BubbleSort: %d\n", cnt);
    cnt = ShellSort(a, 300);
    printf("ShellSort: %d\n", cnt);
    cnt = QuickSort(a, 0, 299);
    printf("QuickSort: %d\n", cnt);
    cnt = MergeSort(a, tmp, 0, 299);
    printf("MergeSort: %d\n", cnt);
    return 0;
}

注意，以上代码只是演示如何统计比较次数，并非完整的排序算法实现，需要根据具体需求进行修改。