数据结构_排序⑤计数排序

2019-08-15 0 条评论 48 次阅读 0 人点赞

计数排序

计数排序在数据范围集中时,效率很高,但是适用范围及场景有限。
时间复杂度:O(MAX(N,范围))
空间复杂度:O(范围)
稳定性:稳定

void CountSort(int* a, int n){
    //范围: min ~ max
    int min = a[0], max = a[0];
    int i;
    //获取数据范围 可有可无 节省空间
    for (i = 1; i < n; ++i){
        if(a[i] < min)
            min = a[i];
        if(a[i] > max)
            max = a[i];
    }
    int range = max - min + 1;
    int* CountArr = (int*)malloc(sizeof(int) * range);
    memset(CountArr, 0, sizeof(int) * range);
    //计数
    for (i = 0; i < n; ++i) {
        CountArr[a[i] - min]++;
    }
    //排序
    int index = 0;
    for (i = 0; i < n; ++i) {
        while(CountArr[i]--){
            a[index] = i + min;
        }
    }
}

void PrintArray(int* a , int n){
    int i;
    for (i = 0; i < n ; ++i) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

L_KingMing

这个人太懒什么东西都没留下

文章评论(0)