題外話計(jì)數(shù)排序時(shí)間性能比之前的排序算法高，在實(shí)際中應(yīng)用較多，只需要O(n)時(shí)間即可完成排序。計(jì)數(shù)排序思想比較巧妙，建議大家對(duì)照課本多學(xué)習(xí)，本文主要給出能運(yùn)行的實(shí)例程序。

[C語(yǔ)言必學(xué)的12個(gè)排序算法：基礎(chǔ)知識(shí) (第0篇）]

線性時(shí)間排序

之前學(xué)習(xí)的快速排序、堆排序、歸并排序都是一類基于比較的排序算法，需要通過(guò)比較關(guān)鍵字大小確定數(shù)據(jù)元素的位置。這類算法最優(yōu)的時(shí)間復(fù)雜度只能到O(nlogn)。

線性時(shí)間排序是一類非比較排序算法，時(shí)間復(fù)雜度O(n)，不需要通過(guò)比較關(guān)鍵字大小即可完成排序。計(jì)數(shù)排序(counting sort)是其中一種。

計(jì)數(shù)排序基本思想

基本思想是給定一個(gè)待排的整數(shù)序列，對(duì)于每一個(gè)數(shù)據(jù)元素，直接存放在保存排序結(jié)果的數(shù)組對(duì)應(yīng)下標(biāo)的位置，例如數(shù)據(jù)元素為5時(shí)，直接存放到數(shù)組a[5]位置，數(shù)據(jù)元素為0時(shí)，直接存放到數(shù)組a[0]的位置。這樣利用待排的數(shù)據(jù)元素和數(shù)組內(nèi)存地址位置建立一一對(duì)應(yīng)關(guān)系，由于數(shù)組內(nèi)存分配是從小到大連續(xù)分配，因此最后直接輸出數(shù)組，即可獲得有序的整數(shù)序列。

計(jì)數(shù)排序?qū)τ谳斎氲臄?shù)據(jù)元素類型有要求，一般是小范圍的整數(shù)或字符，或者很方便利用數(shù)據(jù)元素本身和內(nèi)存地址建立意義對(duì)應(yīng)關(guān)系。對(duì)于n個(gè)整數(shù)輸入序列，確定每個(gè)數(shù)據(jù)元素取值范圍[0-k]，當(dāng)k值小于等于n時(shí)，其時(shí)間復(fù)雜度是O(n)，需要的輔助空間是O(k)，當(dāng)n很小也就是數(shù)據(jù)量很小，但是n取值范圍很大也就是k值很大時(shí)，不適合使用計(jì)數(shù)排序，因?yàn)閮?nèi)存空間浪費(fèi)嚴(yán)重，時(shí)間復(fù)雜度也變成O(k)。

考慮到待排數(shù)據(jù)記錄關(guān)鍵字有重復(fù)，會(huì)出現(xiàn)多次，為保證排序結(jié)果的穩(wěn)定性，因此計(jì)數(shù)排序需要對(duì)出現(xiàn)多次關(guān)鍵字的數(shù)據(jù)進(jìn)行計(jì)數(shù)，保存到數(shù)組對(duì)應(yīng)下標(biāo)的位置，并且根據(jù)該數(shù)組計(jì)數(shù)進(jìn)一步計(jì)算其在排序后的序列的位置。

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

本實(shí)例代碼實(shí)現(xiàn)要點(diǎn)：

1.數(shù)組a[]保存待排的整數(shù)數(shù)據(jù)記錄，數(shù)據(jù)記錄本身就是關(guān)鍵字，每個(gè)整數(shù)的取值范圍[0-k]，最大取值為k。

2.數(shù)組c[]臨時(shí)保存每個(gè)整數(shù)出現(xiàn)的次數(shù)，如果沒(méi)有出現(xiàn)值為0，利用內(nèi)存動(dòng)態(tài)分配，大小為k。

3.數(shù)組b[]用來(lái)臨時(shí)保存排序后的整數(shù)數(shù)據(jù)記錄，最終將數(shù)組b[]的排序結(jié)果復(fù)制到數(shù)組a[]，方便封裝使用。

3.對(duì)數(shù)組c[]的計(jì)數(shù)進(jìn)行累加統(tǒng)計(jì)，從而確定每個(gè)數(shù)據(jù)元素在數(shù)組b[]的位置，特別是重復(fù)出現(xiàn)的數(shù)據(jù)，在數(shù)組b[]中將是一段位置。

/*
#include <stdio.h>
#include <stdlib.h>


void counting_sort(int a[], int length, int k)
{
  // 使用calloc會(huì)自動(dòng)初始化為0
  // 數(shù)組b臨時(shí)保存排序后的數(shù)據(jù)記錄 
  int *b = (int *)calloc(length, sizeof(int));
  // 數(shù)組c對(duì)數(shù)據(jù)記錄關(guān)鍵字進(jìn)行計(jì)數(shù) 
  int *c = (int *)calloc(k, sizeof(int));
  
  int i;
  // 每出現(xiàn)1個(gè)數(shù)據(jù)記錄，對(duì)應(yīng)的數(shù)組位置+1 
  // c[i]表示數(shù)據(jù)等于i的元素個(gè)數(shù) 
  for(i=0; i<length; i++)
    c[a[i]] = c[a[i]] + 1;
  
  // 對(duì)數(shù)組C的計(jì)數(shù)累累加確定排序后位置
  // c[i]表示小于等于i值的數(shù)據(jù)元素個(gè)數(shù)
  for(i=1; i<k; i++)
    c[i] = c[i] + c[i-1]; 
  
  // 將排序結(jié)果輸出到臨時(shí)數(shù)組b中
  for(i=length-1; i>=0; i--)
  {
    // 注意數(shù)組b數(shù)組下標(biāo)從0開始
    // 計(jì)算的實(shí)際位置-1 
    b[c[a[i]]-1] = a[i];
    // 如果數(shù)據(jù)元素重復(fù)出現(xiàn) 
    // 將該元素下一個(gè)保存位置前移 
    c[a[i]] = c[a[i]] - 1;
  } 
  
  // 復(fù)制到數(shù)組a中
  for(i=0; i<length; i++)
    a[i] = b[i]; 
  
  free(b);
  free(c);
}
int main(void)
{
    int a[14] = {4,3,1,2,6,5,0,9,8,7,1,3,0,1};
    counting_sort(a, 14, 10);
    int i;
    for(i=0; i<14; i++)
      printf("%d ", a[i]);
    return 0;
}

其實(shí)做為一個(gè)學(xué)習(xí)者，有一個(gè)學(xué)習(xí)的氛圍跟一個(gè)交流圈子特別重要這里我推薦一個(gè)C/C++基礎(chǔ)交流583650410，不管你是小白還是轉(zhuǎn)行人士歡迎入駐，大家一起交流成長(zhǎng)。