---

前言

計(jì)數(shù)排序是一種 非比較排序。計(jì)數(shù)排序又稱為 鴿巢原理 ，是對哈希直接定址法的變形應(yīng)用。

---

一、計(jì)數(shù)排序算法核心思路

---

映射 概念補(bǔ)充

每個值跟其位置建立出一個關(guān)系

絕對映射

數(shù)值是幾就映射出下標(biāo)是幾。如上圖

若數(shù)組中數(shù)據(jù)的大小范圍并不是乖乖的從0-1，那么這是再采用絕對映射，則會產(chǎn)生很大的空間浪費(fèi)。

那么就有了相對映射的概念

相對映射

通過遍歷原數(shù)組，找出min值，將 a[i] 的值 - min值 【即 a[ i ] - min 】就是對應(yīng) 數(shù)組count[ ]的下標(biāo)了，遍歷到一個就令該下標(biāo)（ 對應(yīng)a[i]的值 ）下的 count [ ] 值++計(jì)數(shù)。

---

二、計(jì)數(shù)排序算法核心實(shí)現(xiàn)步驟

1. 遍歷一遍數(shù)組 => 得出min和max值 => 確定數(shù)的范圍

2. 確定范圍 => 確定需要開辟的數(shù)組的大小

3. 開辟大小為range的空間count [ ] (避免了 絕對映射 那樣的空間的浪費(fèi)) 。用作統(tǒng)計(jì) 需排序的數(shù)組a[i] 中每個數(shù)據(jù)出現(xiàn)的次數(shù)。
   【注意：要進(jìn)行初始化！！否則待會遍歷計(jì)數(shù)數(shù)組中，那些并沒有統(tǒng)計(jì)到有這個數(shù)出現(xiàn)的次數(shù)的位置，將以該內(nèi)存原來的值（隨機(jī)數(shù)）進(jìn)行填入】

4. 遍歷待排序的數(shù)組 => 統(tǒng)計(jì)數(shù)組中每個數(shù)據(jù)出現(xiàn)的次數(shù) => 通過 a[i]-min 找到對應(yīng)下標(biāo)在 count 中的對應(yīng)下標(biāo) => 對該下標(biāo)的值對應(yīng)++進(jìn)行計(jì)數(shù)

5. 遍歷計(jì)數(shù)數(shù)組，根據(jù)統(tǒng)計(jì)到的每個數(shù)的次數(shù)count[i]，就拷貝回去原數(shù)組count[i]次，i+min:對應(yīng)回原數(shù)組中的值，while()循環(huán)覆蓋原數(shù)組

---

三、碼源詳解

//計(jì)數(shù)排序——非比較排序
void CountSort(DataType* a,int n) {//遍歷一遍數(shù)組 => 得出min和max值 => 確定數(shù)的范圍int min = a[0]; int max = a[0];for (int i = 0; i < n; i++) {if (a[i] < min) {min = a[i];}if (max < a[i]) {max = a[i];}//確定范圍 => 確定需要開辟的數(shù)組的大小int range = max - min + 1;    //[min,max]左閉右閉，所以+1//開辟大小為range的空間，避免了 絕對映射 那樣的空間的浪費(fèi)DataType* count = (DataType*)malloc(sizeof(DataType)*range);if (count == NULL) {perror("malloc fail");exit(-1);}//內(nèi)存重置 將count數(shù)組中的值都初始化為0，重置數(shù)組大小為sizeof(DataType) * range//要進(jìn)行初始化，否則待會遍歷計(jì)數(shù)數(shù)組中，那些并沒有統(tǒng)計(jì)到有這個數(shù)出現(xiàn)的次數(shù)的位置，將以該內(nèi)存原來的值（隨機(jī)數(shù)）進(jìn)行填入memset(count, 0, sizeof(DataType) * range);//數(shù)組中的值//遍歷數(shù)組 => 統(tǒng)計(jì)數(shù)組中各數(shù)據(jù)出現(xiàn)的次數(shù) => 通過 a[i]-min 找到對應(yīng)下標(biāo)在 count 中的對應(yīng)下標(biāo) => 對該下標(biāo)的值對應(yīng)++進(jìn)行計(jì)數(shù)for (i = 0; i < n; i++) {count[a[i] - min]++;}//排序//遍歷計(jì)數(shù)數(shù)組，根據(jù)統(tǒng)計(jì)到的每個數(shù)的次數(shù)count[i]，就拷貝回去原數(shù)組count[i]次，覆蓋原數(shù)組//遍歷數(shù)組int j = 0;     //放外面，遍歷a[] j記錄的數(shù)值 不會別被清for (i = 0; i < range; i++) {while (count[i]--){             //count[i]=0的進(jìn)不了循環(huán)a[j++] = i + min;             //i+min:對應(yīng)回原數(shù)組中的值}}}
}

---

四、效率分析

總體特點(diǎn)：比較小眾

1. 適用于數(shù)據(jù)范圍相對集中。
2. 只適合整形
3. 基數(shù)排序

（1）時間復(fù)雜度 — O（Max（N，range））

（2）空間復(fù)雜度 — O（range）