编辑代码

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

void linearCountingSort(int arr[], int n) {
    int max = arr[0], min = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max)
            max = arr[i];
        if (arr[i] < min)
            min = arr[i];
    }

    int range = max - min + 1;
    int* count = (int*)malloc(range * sizeof(int));
    int* temp = (int*)malloc(n * sizeof(int));

    for (int i = 0; i < range; i++) {
        count[i] = 0;
    }

    for (int i = 0; i < n; i++) {
        count[arr[i] - min]++;
    }

    for (int i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }

    for (int i = n - 1; i >= 0; i--) {
        temp[--count[arr[i] - min]] = arr[i];
    }

    for (int i = 0; i < n; i++) {
        arr[i] = temp[i];
    }

    free(count);
    free(temp);
}

int main() {
    int arr[] = {4, 2, 8, 3, 1, 6, 5, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    linearCountingSort(arr, n);
    
    printf("排序后的数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}