• 待排序的數(shù)組A
• 從數(shù)組中取出最大值k
• 新建一個(gè)數(shù)組B，用于存儲(chǔ)排序的輸出
• 新建一個(gè)數(shù)組C，C.length = k+1，用于臨時(shí)存儲(chǔ)空間

原理：
如果A中出現(xiàn)數(shù)m的次數(shù)為n，則C[m] = n，在依據(jù)C對(duì)A輸出到B中。

實(shí)現(xiàn)：

/****************************************************************
 *                              計(jì)數(shù)排序
 ****************************************************************/


/****************************************************************
 * function     : getMaxIndex
 * description  : 獲取數(shù)組中最大值
 * input        : int A[],int length
 * output       : N/A
 * return value : int
 * author       : HanyoungXue
 * date         : 2018-4-18
 *****************************************************************/


int getMax(int A[],int length){
    int max = A[0];

    for (int i = 1; i < length; i++) {
        if (A[i]>max){
            max = A[i];
        }
    }
    return max;
}


/*****************************************************************
 * function     : countingSort
 * description  : 計(jì)數(shù)排序
 * input        : int A[],int B[],int k,int length
 * output       : int B[]
 * return value : N/A
 * author       : HanyoungXue
 * date         : 2018-4-18
 ******************************************************************/

void countingSort(int A[],int B[],int k,int length){
    int C[k+1];
    for (int i = 0; i < k+1; ++i) {
        C[i] = 0;
    }

    for (int j = 0; j < length; ++j) {
        C[A[j]]+=1;
    }

    for (int i = 1; i < k+1; ++i) {
        C[i] +=C[i-1];
    }

    for (int j = 0; j < length; ++j) {
        B[--C[A[j]]] = A[j];
    }
}

/**********************************************************
 * function     : print_array
 * description  : 打印一個(gè)數(shù)組
 * input        : int A[],int length, char *print_string
 * output       : N/A
 * return value : N/A
 * author       : HanyoungXue
 * date         : 2018-4-15
 ***********************************************************/

void print_array(int A[],int length,char *print_string){
    printf("%s\n", print_string);
    for (int i = 0; i < length ; ++i){
        printf("%d\t",A[i]);
    }
    printf("\n");
}



void initARandom(int A[],int length){
    srand(time(NULL));
    for (int i = 0; i < length; ++i) {
        A[i] = rand()%60;
    }
}

int main(int argc, char const *argv[])
{
    int length = 12;
    int A[length];
    /*****************************************
     * 計(jì)數(shù)排序測(cè)試
     *****************************************/

    initARandom(A,length);
    print_array(A,length,"before counting sort:");
    int B[length];
    countingSort(A,B,getMax(A,length),length);
    print_array(B,length,"after counting sort:");


    return 0;
}