用c语言实现计数排序的int函数并在函数内计算每趟排序的时间和所需趟数

计数排序是一种非比较型整数排序算法，它适用于元素范围相对较小的情况。以下是使用 C 语言实现计数排序的 `counting_sort` 函数，同时在内部计算每趟排序的时间和所需的趟次数。由于 C 语言本身没有内置时间测量功能，这里我们将使用 `clock()` 函数作为简单的计时器，并假设每趟排序就是一次数组扫描和计数的过程。请注意，实际的时间复杂度和计算会受到计算机硬件及操作系统的影响。

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

#define MAX 100 // 假设最大元素不超过100

void counting_sort(int arr[], int n) {
    int output[MAX + 1] = {0}; // 输出数组
    int count[MAX + 1] = {0}; // 计数数组
    int i, j;
    
    // 初始化计数数组，所有元素计数初始化为0
    for (i = 0; i <= MAX; i++)
        count[i] = 0;

    // 统计每个元素的出现次数
    for (i = 0; i < n; i++) {
        count[arr[i]]++;
    }

    // 更新输出数组，累计每个元素的计数值
    for (i = 1; i <= MAX; i++) {
        count[i] += count[i - 1];
    }

    // 将原数组按照计数顺序填充到输出数组
    for (i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i]; // 注意索引减一
        count[arr[i]]--;
    }

    // 将排序后的结果复制回原数组
    for (i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// 使用 clock() 函数获取当前时间，这里只作为一个示例，无法提供精确的测量
double get_time_in_milliseconds() {
    struct timespec start, end;
    double elapsed;
    clock_gettime(CLOCK_MONOTONIC, &start);
    // 排序操作...
    clock_gettime(CLOCK_MONOTONIC, &end);
    elapsed = difftime(end.tv_sec, start.tv_sec) + 1e-9 * (end.tv_nsec - start.tv_nsec);
    return elapsed * 1e3; // 返回毫秒
}

int main() {
    int arr[] = {5, 2, 8, 1, 9, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    clock_t start = clock();

    counting_sort(arr, n);

    double time_taken = get_time_in_milliseconds();
    printf("排序后数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n\n总趟数: 1 (计数排序不需要额外的遍历)\n时间消耗: %.3f ms\n", time_taken);

    return 0;
}

在这个例子中，`get_time_in_milliseconds` 函数仅用于展示如何获取时间，实际应用中可能需要引入更专业的性能分析库来获得更准确的测量。注意，计数排序的趟数通常被看作是1次，因为它只是一次扫描过程。