编辑代码

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

void linear_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]++;
    }
    
    // 对count数组进行累加操作
    for (int i = 1; i < count_size; i++) {
        count[i] += count[i - 1];
    }
    
    // 创建结果数组sorted_arr
    int* sorted_arr = (int*)malloc(n * sizeof(int));
    
    // 将元素放置在sorted_arr数组中的正确位置
    for (int i = n - 1; i >= 0; i--) {
        sorted_arr[count[arr[i] - min_val] - 1] = arr[i];
        count[arr[i] - min_val]--;
    }
    
    // 将排序后的数组复制回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = sorted_arr[i];
    }
    
    free(count);
    free(sorted_arr);
}

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");

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