線性時(shí)間排序--計(jì)數(shù)和基數(shù)排序-創(chuàng)新互聯(lián)

1、計(jì)數(shù)排序

創(chuàng)新互聯(lián)建站是一家企業(yè)級(jí)云計(jì)算解決方案提供商,超15年IDC數(shù)據(jù)中心運(yùn)營(yíng)經(jīng)驗(yàn)。主營(yíng)GPU顯卡服務(wù)器，站群服務(wù)器，服務(wù)器托管，海外高防服務(wù)器，機(jī)柜大帶寬租用·托管，動(dòng)態(tài)撥號(hào)VPS，海外云手機(jī)，海外云服務(wù)器，海外服務(wù)器租用托管等。

 (1)、算法思想

 是一組在特定范圍內(nèi)的整數(shù)，在線性時(shí)間內(nèi)排序，比nlog(n)更快的排序算法；

 較小范圍內(nèi)是比較好的排序算法，如果很大是很差的排序算法；

 可以解決重復(fù)元素的出現(xiàn)的排序算法；

 (2)、代碼實(shí)現(xiàn)

#include<stdio.h>

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)、結(jié)果截圖

 (4)、算法分析：

 計(jì)數(shù)排序優(yōu)點(diǎn)：穩(wěn)定性(一個(gè)穩(wěn)定性算法保證了相等元素的順序)；

 時(shí)間復(fù)雜度：O(n)；

2、基數(shù)排序

 (1)、算法思想

 i、從最后一位(低位-->高位)開(kāi)始排序，并且的是穩(wěn)定的排序算法(輔助算法：計(jì)數(shù)排序)，整體思想：按位排序；

 ii、在進(jìn)行基數(shù)排序時(shí)，從個(gè)位--->十位--->百位......每取一位時(shí)，分別進(jìn)行計(jì)數(shù)排序，傳的參數(shù)：位、要排序的總數(shù)、新的結(jié)果、輔助空間(開(kāi)辟10個(gè)元素的空間)、原先數(shù)組；利用位和輔助空間，將原先數(shù)組的值放入新的結(jié)果空間中即可；(位的順序與原先結(jié)果的順序保持一致)!!!

 iii、基數(shù)排序只要知道大數(shù)是幾位，進(jìn)行幾次排序即可；

 (2)、代碼實(shí)現(xiàn)

#include<stdio.h>
#include<malloc.h>

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;

    //從個(gè)位-->十位-->百位,每一次調(diào)用這個(gè)函數(shù),輔助空間都必須初始化為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;

    //個(gè)位進(jìn)行排序
    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:代表要排的數(shù)字;newA:代表最終排行的新空間
                                      // c:代表輔助空間 a:代表原先數(shù)字
    for(i = 0; i < count; i++){
        a[i] = newA[i];
    }

    //十位進(jìn)行排序
    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)、運(yùn)行結(jié)果

 (4)、算法分析

 時(shí)間復(fù)雜度：O(n);

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

網(wǎng)站題目：線性時(shí)間排序--計(jì)數(shù)和基數(shù)排序-創(chuàng)新互聯(lián)
URL標(biāo)題：http://muchs.cn/article46/dpihhg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供建站公司、電子商務(wù)、網(wǎng)站策劃、品牌網(wǎng)站制作、網(wǎng)站維護(hù)、網(wǎng)站營(yíng)銷

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)