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

為靈石等地區(qū)用戶提供了全套網(wǎng)頁(yè)設(shè)計(jì)制作服務(wù)，及靈石網(wǎng)站建設(shè)行業(yè)解決方案。主營(yíng)業(yè)務(wù)為成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作、靈石網(wǎng)站設(shè)計(jì)，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠(chéng)的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會(huì)得到認(rèn)可，從而選擇與我們長(zhǎng)期合作。這樣，我們也可以走得更遠(yuǎn)！

  (1)、算法思想

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

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

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

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

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

  (4)、算法分析：

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

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

2、基數(shù)排序

  (1)、算法思想

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

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

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

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

#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;

    //從個(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);