#include "stdio.h"


int GetMaxnum(int arr[], int length){
    int max_ele = arr[0];
    for(int i = 0; i < length; i++){
        if(arr[i] > max_ele){
            max_ele = arr[i];
        }
    }
    return max_ele;
}


int GetMinnum(int arr[], int length){
    int min_ele = arr[0];
    for(int i = 0; i < length; i++){
        if(arr[i] < min_ele){
            min_ele = arr[i];
        }
    }
    return min_ele;
}


void count_sort(int arr[], int length){
    int max_num = GetMaxnum(arr, length);
    int min_num = GetMinnum(arr, length);
    int range = max_num - min_num + 1;

//    存储数字的数组，range就是其长度
    int count[range];
//    输出的数组
    int output[length];
    //初始化存储的数组
    for(int start = 0; start < range; start++){
        count[start] = 0;
    }
    //进行存储操作
    for(int j = 0; j < length; j++){
        count[arr[j] - min_num]++;
    }
//   计数操作
    for(int i = 1; i < range; i++){
        count[i] += count[i - 1];
    }
//    找到索引和对应的值
    for(int k = length - 1; k >= 0; k--){
        output[count[arr[k] -min_num] -1] = arr[k];
        count[arr[k] - min_num]--;
    }

    for (int m = 0; m < length; m++) {
        arr[m] = output[m];
    }
}


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


int main(){
    int arr[] = {1, 3, 2, 4, 1, 2, 3, 1, 3, 5};
//    int arr[] = {8, 32, 22, 73, 95, 13, 9, 82, 23, 46, 71, 52, 90, 53, 77, 75, 65, 64, 74, 24};
    int length = sizeof (arr) / sizeof (arr[0]);
    printf("before:\n");
    display(arr, length);
    printf("======\n");
    printf("after:\n");
    count_sort(arr, length);
    display(arr, length);
    return 0;
}