编辑代码

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

void counting_sort(int arr[], int n) {
    // 找到最大值和最小值
    int min_val = arr[0];
    int max_val = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] < min_val) {
            min_val = arr[i];
        }
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
    }
    
    // 创建辅助数组count，并初始化为0
    int count_size = max_val - min_val + 1;
    int* count = (int*)malloc(count_size * sizeof(int));
    for (int i = 0; i < count_size; i++) {
        count[i] = 0;
    }
    
    // 统计每个元素出现的次数
    for (int i = 0; i < n; i++) {
        count[arr[i] - min_val]++;
    }
    
    // 生成排序后的数组
    int sorted_index = 0;
    for (int i = 0; i < count_size; i++) {
        while (count[i] > 0) {
            arr[sorted_index++] = i + min_val;
            count[i]--;
        }
    }
    
    free(count);
}

int main() {
    int arr[] = {5, 2, 9, 1, 5, 6, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("原始数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    counting_sort(arr, n);
    
    printf("排序后数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    return 0;
}