思想：計(jì)數(shù)排序其實(shí)是桶排序的一種特殊情況。所處排序范圍是固定的，比如最大值是 k，我們就可以把數(shù)據(jù)劃分成 k 個(gè)桶。每個(gè)桶內(nèi)的數(shù)據(jù)值都是相同的，省掉了桶內(nèi)排序的時(shí)間。這里的k是小于數(shù)據(jù)總數(shù)的。

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

// 計(jì)數(shù)排序
void countSort(int a[], int n) {
    if (n <= 1) {
        return;
    }
    
    // 求解最大值
    int max = a[0];
    for(int i = 1; i < n; i++) {
        if (max < a[i]) {
            max = a[i];
        }
    }
    
    // 初始化數(shù)組， 用來計(jì)數(shù)
    int c[max];
    for (int i = 0; i <= max; i++) {
        c[i] = 0;
    }
    
    // 開始計(jì)數(shù)， 計(jì)算每個(gè)桶內(nèi)的個(gè)數(shù)
    for (int i = 0; i < n; i++) {
        c[a[i]]++;
    }
    
    // 依次做累加， 實(shí)現(xiàn)排序
    for (int i = 1; i <= max; i++) {
        c[i] = c[i - 1] + c[i];
    }
    
    // 臨時(shí)數(shù)組， 用來排序
    int r[n];
    for (int i = n - 1; i >= 0; i--) {
        int index = c[a[i]] - 1;
        r[index] = a[i];
        c[a[i]]--;
    }
    
    // 將臨時(shí)數(shù)組值， 賦值給原始數(shù)組
    for (int i = 0; i < n; i++) {
        a[i] = r[i];
    }
}

使用

int a[] = {2, 5, 3, 0, 2, 3, 0 ,3};
    int num = sizeof(a) / sizeof(int);
    countSort(a, num);
    
    for (int i = 0; i < num; i++) {
        printf("%d\n", a[i]);
    }