编辑代码

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

// 计数排序函数
void counting_sort(int arr[], int n) {
    // 寻找数组中的最大值来确定计数数组的长度
    int max_val = 0;
    for (int i = 0; i < n; i++) {
        if(arr[i] > max_val) {
            max_val = arr[i];
        }
    }
    
    // 初始化计数数组，大小为最大值加1，并填充为0
    int* count = (int*)calloc(max_val + 1, sizeof(int));
    
    // 对每个元素计数
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }
    
    // 将计数数组的值累加
    for (int i = 1; i <= max_val; i++) {
        count[i] += count[i - 1];
    }
    
    // 排序数组的存储
    int* sorted = (int*)malloc(n * sizeof(int));
    
    // 对原数组进行排序，从后向前以保证稳定性
    for (int i = n - 1; i >= 0; i--) {
        sorted[--count[arr[i]]] = arr[i];
    }
    
    // 将排序好的数组复制回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = sorted[i];
    }
    
    // 释放内存
    free(count);
    free(sorted);
}

// 主函数，用于测试计数排序
int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("Original array:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    // 调用计数排序
    counting_sort(arr, n);
    
    printf("Sorted array:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    return 0;
}