线性排序算法 --- 计数排序，基数排序，桶排序

计数排序应用:

线性排序算法计数排序应该挺好理解的，每次把数字出现的次数记录下来，然后做成前缀，前缀就是小于等于当前数的个数。

比如 2,3,0,3,6,2,3,5，首先记录出现次数

0 1 2 3 4 5 6

1 0 2 3 0 1 1

然后对这个数组做一个前缀

c[0] c[1] c[2] c[3] c[4] c[5] c[6]
1 1 3 6 6 7 8

就是这样，然后排序的时候就输出数字对应的地方

如 a[i]= 5 那么 b[c[a[i]]]=a[i]; 把b 数组里面 7的位置赋值为5.然后小于等于5的数量-1；

 #include<bits/stdc++.h>
using namespace std;
int a[8]= {2,3,0,3,6,2,3,5};
int b[8];
int c[7];

int main() {
    for(int i=0; i<8; i++) {
        c[a[i]]++;
    }
    for(int i=1; i<7; i++) {   //把这个for倒过来就是从大到小
        c[i]=c[i-1]+c[i];
    }
    printf("C数组:\n");
    for(int i=0; i<7; i++) {
        printf("c[%d]\t",i);
    }
    printf("\n");
    for(int i=0; i<7; i++) {
        printf(" %d\t",c[i]);
    }
    printf("\n");
    printf("排序过程\n");
    for(int i=7; i>=0; i--) {
        b[--c[a[i]]]=a[i];
        for(int i=0; i<7; i++) {
            printf("%d ",b[i]);
        }
        printf("\n");
    }
    return 0;
}

基数排序：

实际上和计数排序没啥太大的区别，计数排序如果数太大，你 C数组的就要浪费非常大的内存，或者根本开不了这么大的内存。

基数排序，就是把每个位拆分出来，实际上和计数排序差距不大。

12,13,120,33,46,52,3,25

120 12 52 13 33 3 25 46

以最后一位递增

3 12 13 120 25 33 46 52

在最后一位为递增基础上倒数第2位递增

3 12 13 25 33 46 52 120

最后以第一位递增，就是排序好的

 #include<bits/stdc++.h>
using namespace std;
int a[8]= {12,13,120,33,46,52,3,25};
int b[8];
int c[10];
int main() {
    int mx=0,pos=0,cot=1;
    for(int i=0; i<8; i++) {
        mx=max(mx,a[i]);
    }
    while(mx/cot>0) {
        memset(c,0,sizeof(c));
        for(int i=0; i<8; i++) {
            c[a[i]/cot%10]++;
        }
        for(int i=1; i<10; i++) {   //把这个for倒过来就是从大到小
            c[i]=c[i-1]+c[i];
        }
        printf("计数数组:\n");
        for(int i=0; i<10; i++) {
            printf("c[%d]\t",i);
        }
        printf("\n");
        for(int i=0; i<10; i++) {
            printf(" %d\t",c[i]);
        }
        printf("\n");
        printf("排序第%d位结果:\n",pos);
        for(int i=7; i>=0; i--) {
            b[--c[a[i]/cot%10]]=a[i];
        }
        for(int i=0; i<8; i++) {
            a[i]=b[i];
        }
        for(int i=0;i<8;i++){
            printf("%d ",a[i]);
        }
        puts("");
        cot*=10;
        pos++;
    }
    return 0;
}

桶排序，实际上和计数排序也差不多，但是到目前位置我还没用过。

计数排序就相当于桶的大小为 1 的排序。（基数排序实际上有点类似于以10 的桶里面套着一个10 的桶）个人理解

开一个桶的大小 b 然后把他一个数x丢到 x/b 那个桶里面去，然后把每个桶里面排序。把桶分成1不就是计数排序。。个人理解

理论上来说：在分布桶均匀的情况下，是O(n+n*(2-1/n));

有些情况下可能退化成普通排序一样的复杂度。

代码就不敲了，还没用过。。。。

J - Jeronimo’s List