非比较排序——计数排序

简介步骤图解code

计数排序是一种稳定的线性时间排序算法当输入的元素是n个 0到k 之间的整数时，它的运行时间是O(n+k)计数排序处理小数据量很好用，也可以与其他排序结合使用计数排序对于数据范围很大的数组，需要大量时间和内存计数排序可以帮助入门者更好的理解栈与哈希的巧用 步骤

将每个待排序元素存入数组a，使a在有效范围内每一个元素都对应着一个待排序元素遍历a数组每个元素，因为其有一一对应的值，所以cnt数组为计数器利用栈，将a数组中的元素变为升序输出

例如排序 2 1 1 1 3
code

这里的代码会很臃肿，但计数排序的思想能够很好的体现

#include 
#include 

#define maxn 1000001
#define maxk 100001

int a[maxn];
int cnt[maxk]; //开辟了很多无用空间，会浪费掉很多内存空间

void Input(int n, int *a) {
    for(int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
}

void CountingSort(int n, int *a) {
    int i, top; 
    memset(cnt, 0, sizeof(cnt));
    for(i = 0; i < n; ++i) {       		 //遍历a数组每个元素
        ++cnt[ a[i] ];                   //相应数的计数器 加一
    }
    top = 0；
    for(i = 0; i < maxk; ++i) {
        while(cnt[i]) {
            a[top++] = i;                //以升序顺序放入
            --cnt[i];
        }
        if(top == n) {                   //循环结束
            break;
        }
    }
}

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

int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
        Input(n, a);
        CountingSort(n, a);
        Output(n, a);
    }
    return 0;
} 

参考:

1.8 计数排序计数排序