编辑代码

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


void findMinMax(int arr[], int len, int* min, int* max) {
    *min = arr[0];
    *max = arr[0];

    for(int i = 1; i < len; ++i) {  //循环查找最小值和最大值
        if (arr[i] < *min) {
            *min = arr[i];
        }
        else if (arr[i] > *max) {
            *max = arr[i];
        }
    } 
}

//线性计数排序
void lineCountSort(int arr[], int len, int orderedArr[]) {
    int min, max;
    findMinMax(arr, len, &min, &max);   //查找最小值和最大值
    
    int countLen = max - min + 1;   //计数数组的长度
    int *count = (int*)malloc(countLen * sizeof(int));  //创建计数数组
    
    for (int i = 0; i < countLen; ++i) {    //初始化计数数组为0
        count[i] = 0;
    } 
    
    for (int i = 0; i < len; ++i) {         //统计每个元素出现的次数
         ++count[arr[i] - min];
    } 
    
    for (int i = 1; i < countLen; ++i ){    //计算小于等于每个元素的元素个数
        count[i] = count[i] + count[i-1];
    }
    
    for (int i = len-1; i >= 0; --i) {      //利用计数数组进行排序
        orderedArr[--count[arr[i] - min]] = arr[i];
    } 
}

void printArray(int arr[], int len) {
    for (int i = 0; i < len; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {62, 47, 84, 96, 62, 47, 96, 96};
    int orderedArr[8];
    
    printArray(arr, 8);
    lineCountSort(arr, 8, orderedArr);
    printArray(orderedArr, 8);
    
    return 0;
}