计数排序应用:

J - Jeronimo's List

 Gym - 101466J 

http://codeforces.com/gym/101466/problem/J

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

比如   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));

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

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