01

—

計數(shù)排序原理

假設(shè)輸入n個元素，每個元素在區(qū)間0~k內(nèi)的一個整數(shù)，區(qū)間k是最大值和最小值之間的區(qū)間。假如輸入元素最大值是5，最小值是2，那么區(qū)間k=5 - 2 1 = 4。

計數(shù)排序算法思想：對于每一個輸入元素x，確定小于等于元素x的個數(shù)，按照小于等于元素x的個數(shù)確定元素x在輸出序列的索引。當(dāng)有相同元素時，相同的元素要依次排列。

02—

計數(shù)排序?qū)崿F(xiàn)

現(xiàn)有序列[6, 3, 6, 1, 9, 5]，采用計數(shù)排序算法對序列進行排序。為了方便充分理解計數(shù)排序算法思想，我們做了如下圖，詳細表示計數(shù)排序過程，原始序列如下圖所示。

求出序列最大值max和最小值min，進而求出序列元素所在區(qū)間k = max - min 1，再求出小于等于元素x的個數(shù)。

小于元素x的個數(shù)正是元素x在輸出序列中對應(yīng)的索引（索引從0開始），考慮到序列可有相同的元素，同時又要保持Q(n)的時間復(fù)雜度，新建一個k大小的緩沖區(qū)，依次保存各個元素對應(yīng)的索引值，如下圖所示。

圖中-1的索引表示無效索引，最后遍歷原始序列，按照各個元素的對應(yīng)的索引存放在輸出序列中，相同元素依次排列，對應(yīng)k區(qū)間內(nèi)的保存的索引值加1。最終輸出序列如下圖所示。

計數(shù)排序算法實現(xiàn)代碼如下：

void?count_sort(int?*input, int?input_length, int?*output, int?output_length){
????if(input == NULL?|| output == NULL?|| output_length < input_length){
????????return;
????}

????int?k = 0, max, min;
????int?i = 0;

????min = input[0];
????max = input[0];
????//找出最大值和最小值
????for(i = 0; i < input_length; i ){
????????if(input[i] < min){
????????????min = input[i];
????????}
????????if(input[i] > max){
????????????max = input[i];
????????}
????}
????k = max - min 1; //求出數(shù)值區(qū)間
????int?*temp = (int?*)malloc(sizeof(int) * k);
????int?*index = (int?*)malloc(sizeof(int) * k);
????if(temp == NULL){
????????return;
????}
????memset(temp, 0, sizeof(int) * k);
????memset(index, -1, sizeof(int) * k);
????int?count = 0;
????for(i = 0; i < input_length; i ){
????????temp[input[i] - min] ; //統(tǒng)計input里每個元素的個數(shù)
????}

????for(i = 0; i <= k; i ){
????????count = temp[i];
????????if(i > 0){
????????????temp[i] = temp[i] temp[i - 1]; //統(tǒng)計input小于等于各個元素值的個數(shù)
????????}
????????if(count > 0){
????????????index[i] = temp[i] - count; //求出各個元素在輸出序列中對應(yīng)的索引值
????????}
????}
????for(i = input_length - 1; i >= 0; i--){
????????output[index[input[i] - min]] = input[i]; //將原始序列中的元素存放在輸出序列對應(yīng)索引中
????????index[input[i] - min] ; //相同的數(shù)據(jù)相鄰放置
????????temp[input[i] - min]--;
????}
????free(temp);
????free(index);
}寫一個小程序驗證計數(shù)排序算法的正確性。

#include?
#include?"count_sort.h"

#define?MAX_LENGTH 10

int?main()?{
????int?input[MAX_LENGTH] = {1, 2, -3, 6, 7, 9, 3, 5, 4, 2};
????int?output[MAX_LENGTH] = {0};

????count_sort(input, MAX_LENGTH, output, MAX_LENGTH);
????int?i = 0;
????printf("計數(shù)排序輸出結(jié)果\n");
????for(i = 0; i < MAX_LENGTH; i ){
????????printf("%d ", output[i]);
????}
????printf("\n");

????return?0;
}
編譯運行輸出如下：

計數(shù)排序輸出結(jié)果
-3 1 2 2 3 4 5 6 7 9

算法完全正確。