线性时间排序--计数和基数排序-创新互联

1、计数排序

创新互联建站是一家企业级云计算解决方案提供商,超15年IDC数据中心运营经验。主营GPU显卡服务器,站群服务器,服务器托管,海外高防服务器,机柜大带宽租用·托管,动态拨号VPS,海外云手机,海外云服务器,海外服务器租用托管等。

 (1)、算法思想

 是一组在特定范围内的整数,在线性时间内排序,比nlog(n)更快的排序算法;

 较小范围内是比较好的排序算法,如果很大是很差的排序算法;

 可以解决重复元素的出现的排序算法;

 (2)、代码实现

#include

void countSort(int *a, int count);
void showArray(int *a, int count);

void showArray(int *a, int count){
    int i;

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

void countSort(int *a, int count){
    int b[10] = {0};
    int *c;
    int i;

    c = (int *)malloc(sizeof(int) * count);
    for(i = 0; i < count; i++){
        b[a[i]]++;
    }
    for(i = 1; i < 10; i++){
        b[i] += b[i-1];
    }

    for(i = count-1; i >= 0; i--){
        c[b[a[i]]-1] = a[i];
        b[a[i]]--;
    }

    for(i = 0; i < count; i++){
        a[i] = c[i];
    }

    free(c);

}
void main(void){
    int a[] = {2, 4, 7, 2, 1, 0, 9};
    int count = sizeof(a)/sizeof(int);

    countSort(a, count);
    showArray(a, count);
}

 (3)、结果截图

线性时间排序--计数和基数排序

 (4)、算法分析:

 计数排序优点:稳定性(一个稳定性算法保证了相等元素的顺序);

 时间复杂度:O(n);

2、基数排序

 (1)、算法思想

 i、从最后一位(低位-->高位)开始排序,并且的是稳定的排序算法(辅助算法:计数排序),整体思想:按位排序;

 ii、在进行基数排序时,从个位--->十位--->百位......每取一位时,分别进行计数排序,传的参数:位、要排序的总数、新的结果、辅助空间(开辟10个元素的空间)、原先数组;利用位和辅助空间,将原先数组的值放入新的结果空间中即可;(位的顺序与原先结果的顺序保持一致)!!!

 iii、基数排序只要知道大数是几位,进行几次排序即可;

 (2)、代码实现

#include
#include

void radixSort(int *a, int count);
void countSort(int *bitNumber, int count, int *newA, int *c, int *a);
void showArray(int *a, int count);

void showArray(int *a, int count){
    int i;

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

void countSort(int *bitNumber, int count, int *newA, int *c, int *a){
    int i;

    //从个位-->十位-->百位,每一次调用这个函数,辅助空间都必须初始化为0;
    for(i = 0; i < 10; i++){
        c[i] = 0;
    }

    for(i = 0; i < count; i++){
        c[bitNumber[i]]++;
    }

    for(i = 1; i < 10; i++){
        c[i] += c[i-1];
    }

    for(i = count-1; i >= 0; i--){
        newA[c[bitNumber[i]]-1] = a[i];  //a[i]与原先所取的位顺序一致
        c[bitNumber[i]]--;
    }
}

void radixSort(int *a, int count){
    int *bitNumber;
    int *newA;
    int c[10] = {0};
    int i;

    //个位进行排序
    bitNumber = (int *)malloc(sizeof(int) * count);
    newA = (int *)malloc(sizeof(int) * count);
    for(i = 0; i < count; i++){
        bitNumber[i] = a[i]%10;
    }
    countSort(bitNumber, count, newA, c, a);  //bitNumber:代表要排的数字;newA:代表最终排行的新空间
                                      // c:代表辅助空间 a:代表原先数字
    for(i = 0; i < count; i++){
        a[i] = newA[i];
    }

    //十位进行排序
    for(i = 0; i < count; i++){
        bitNumber[i] = a[i]/10%10;
    }
    countSort(bitNumber, count, newA, c, a);                      
    for(i = 0; i < count; i++){
        a[i] = newA[i];
    }

    //百位排序
    for(i = 0; i < count; i++){
        bitNumber[i] = a[i]/100%10;
    }
    countSort(bitNumber, count, newA, c, a);  
                                     
    for(i = 0; i < count; i++){
        a[i] = newA[i];
    }
    //千位排序
    for(i = 0; i < count; i++){
        bitNumber[i] = a[i]/1000%10;
    }
    countSort(bitNumber, count, newA, c, a);  
                                     
    for(i = 0; i < count; i++){
        a[i] = newA[i];
    }

}

void main(void){
    int a[] = {23, 1000, 90, 34, 2, 6, 3, 444, 555, 666, 777, 888, 999, 111, 222};
    int count = sizeof(a)/sizeof(int);
    radixSort(a, count);
    showArray(a, count);
}

 (3)、运行结果

线性时间排序--计数和基数排序

 (4)、算法分析

 时间复杂度:O(n);

另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


网页名称:线性时间排序--计数和基数排序-创新互联
网站地址:http://myzitong.com/article/dpihhg.html