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

計(jì)數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲在額外開辟的數(shù)組空間中。作為一種線性時間復(fù)雜度的排序，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。

1. 計(jì)數(shù)排序的特征

當(dāng)輸入的元素是 n 個 0 到 k 之間的整數(shù)時，它的運(yùn)行時間是 Θ(n + k)。計(jì)數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。
由于用來計(jì)數(shù)的數(shù)組C的長度取決于待排序數(shù)組中數(shù)據(jù)的范圍（等于待排序數(shù)組的最大值與最小值的差加上1），這使得計(jì)數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組，需要大量時間和內(nèi)存。例如：計(jì)數(shù)排序是用來排序0到100之間的數(shù)字的最好的算法，但是它不適合按字母順序排序人名。但是，計(jì)數(shù)排序可以用在基數(shù)排序中的算法來排序數(shù)據(jù)范圍很大的數(shù)組。
通俗地理解，例如有 10 個年齡不同的人，統(tǒng)計(jì)出有 8 個人的年齡比 A 小，那 A 的年齡就排在第 9 位,用這個方法可以得到其他每個人的位置,也就排好了序。當(dāng)然，年齡有重復(fù)時需要特殊處理（保證穩(wěn)定性），這就是為什么最后要反向填充目標(biāo)數(shù)組，以及將每個數(shù)字的統(tǒng)計(jì)減去 1 的原因。

2.算法步驟

• 找出待排序的數(shù)組中最大和最小的元素
• 統(tǒng)計(jì)數(shù)組中每個值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)
• 對所有的計(jì)數(shù)累加（從C中的第一個元素開始，每一項(xiàng)和前一項(xiàng)相加）
• 反向填充目標(biāo)數(shù)組：將每個元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個元素就將C(i)減去1

countingSort.gif

3.代碼

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void
print_arr(int *arr, int n)
{
    int i;
    printf("%d", arr[0]);
    for (i = 1; i < n; i++)
        printf(" %d", arr[i]);
    printf("\n");
}

void
counting_sort(int *ini_arr, int *sorted_arr, int n)
{
    int *count_arr = (int *) malloc(sizeof(int) * 100);
    int i, j, k;
    for (k = 0; k < 100; k++)
        count_arr[k] = 0;
    for (i = 0; i < n; i++)
        count_arr[ini_arr[i]]++;
    for (k = 1; k < 100; k++)
        count_arr[k] += count_arr[k - 1];
    for (j = n; j > 0; j--)
        sorted_arr[--count_arr[ini_arr[j - 1]]] = ini_arr[j - 1];
    free(count_arr);
}

int main(int argc, char **argv)
{
    int n = 10;
    int i;
    int *arr = (int *) malloc(sizeof(int) * n);
    int *sorted_arr = (int *) malloc(sizeof(int) * n);
    srand(time(0));
    for (i = 0; i < n; i++)
        arr[i] = rand() % 100;
    printf("init_array: ");
    print_arr(arr, n);
    counting_sort(arr, sorted_arr, n);
    printf("sorted_array: ");
    print_arr(sorted_arr, n);
    free(arr);
    free(sorted_arr);
    return 0;
}

轉(zhuǎn)載于菜鳥教程

2020.11.18 11:45 深圳