我們之前文章里面講到的排序基本上都是比較排序，不管是冒泡排序、快速排序還是插入排序等等，都是基于元素之間的比較來進(jìn)行一個(gè)整體的排序，那有沒有一種排序是可以不用進(jìn)行元素間的對比就可以完成整個(gè)序列的升序或者降序呢？當(dāng)然有，計(jì)數(shù)排序就不用元素之間的相互比較，而是通過元素的下標(biāo)來確定每個(gè)元素的位置從而進(jìn)行排序，在某些特殊的時(shí)候，它的排序速度甚至比快速排序還要快。

舉個(gè)例子，現(xiàn)在有一組待排序的數(shù)字（如圖1-1所示），怎么通過計(jì)數(shù)排序進(jìn)行升序排序呢？

首先，通過觀察我們會發(fā)現(xiàn)數(shù)組里的元素的取值范圍為0——9，于是我們可以創(chuàng)建一個(gè)長度為9（元素最大值）的數(shù)組，元素的初始值都為0，如圖1-2所示：

遍歷原始數(shù)組，讓每一個(gè)整數(shù)按照值對號入座，對應(yīng)數(shù)組下標(biāo)的元素加1，第一個(gè)元素為8，就在數(shù)組下標(biāo)為8的元素加1（如圖1-3所示）

按照此方法，依次遍歷后面的元素，最后得到的結(jié)果如圖1-4所示：

最后，按照下標(biāo)的先后順序依次將下標(biāo)輸出，該下標(biāo)的元素是幾，就將下標(biāo)輸出幾次，最后就會得到一個(gè)順序?yàn)樯虻臄?shù)組，如圖1-5所示：

其實(shí)從上面的步驟中可以看出來計(jì)數(shù)排序是比較簡單的排序，效率也是比較高的，但是他還是有一定的局限性，只適合一些特殊的序列，元素?cái)?shù)值跨度不能太大，范圍最好在0~100之間，一組數(shù)值比較相鄰的待排序序列更加適合用計(jì)數(shù)排序。

以上呢，就是對最基礎(chǔ)版的計(jì)數(shù)排序的詳細(xì)解釋，接下來我們來看一下怎么把這些步驟通過C語言進(jìn)行實(shí)現(xiàn)。

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

#include <stdio.h>

void sort(int *A, int *B, int len, int k)

{

? ? ? ? ? ? int C[k+1], i, value, pos;? // 定義一個(gè)數(shù)組C，為輔助數(shù)組

? ? ? ? ? ? for(i=0; i<=k; i++)? // 為C數(shù)組進(jìn)行初始化，元素值都為0

? ? ? ? ? ? {

? ? ? ? ? ? ? ? C[i] = 0;

? ? ? ? ? ? }

? ? ? ? ? ? for(i=0; i< len; i++)? // 統(tǒng)計(jì)A數(shù)組中i元素的個(gè)數(shù)

? ? ? ? ? ? {

? ? ? ? ? ? ? ? C[A[i]] ++;?

? ? ? ? ? ? }

? ? ? ? ? ? for(i=1; i<=k; i++)? // 統(tǒng)計(jì)A元素中小于等于I元素的個(gè)數(shù)?

? ? ? ? ? ? {

? ? ? ? ? ? ? ? C[i] = C[i] + C[i-1];

? ? ? ? ? ? }

? ? ? ? ? ? for(i=len-1; i>=0; i--)? // 進(jìn)行排序，將排完序的值放到B數(shù)組中

? ? ? ? ? ? {

? ? ? ? ? ? ? ? value = A[i];

? ? ? ? ? ? ? ? pos = C[value];

? ? ? ? ? ? ? ? B[pos-1] = value;

?C[value]--;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? }

}

int main()

{

?//定義一個(gè)原始數(shù)組A，長度為9? 定義一個(gè)數(shù)組B，用來存儲排完序的元素

? ? ? ? ? ? int A[9] = {8,4,5,7,3,6,1,0,9}, B[9], i;

? ? ? ? ? ? sort(A, B, 9, 9);? ? // 調(diào)用sort函數(shù)，傳四個(gè)參數(shù)：數(shù)組A、數(shù)組B 、數(shù)組長度、最大元素值

? ? ? ? ? ? for (i=0; i<= 8; i++)

? ? ? ? ? ? {

? ? ? ? ? ? ? ? printf("%d ", B[i]);

? ? ? ? ? ? }

? ? ? ? ? ? printf("\n");

? ? ? ? ? ? return 0;

}

原文來源：學(xué)到牛牛 www.xuedaon.com