閱讀659 返回首頁    go 阿裏雲 go 技術社區[雲棲]

經典算法之計數排序

一 引言
計數排序假設n個輸入元素中的每一個都是介於0-k的整數，此處k為某個整數。當k等於O（n）時，計數排序的運行時間為Θ（n）。
二 基本思想
計數排序的基本思想就是對每一個輸入元素x，確定小於x的元素個數。因此我們就可以直接把x放到最終輸出數組中的相應位置上。
例如：
如果有17個元素小於x，則x就位於第18個輸出的位置上。當然有幾個元素相同時，這個方法就略微改進一下，因為不能將它們放在同一個位置上。
三 具體實現

假定輸入數組為A[1..n]，他們的值均位於0~k之間，輸出排序之後的數組為B[1..n]，以及臨時存儲數組C[0..k]。計數排序的偽代碼如下：
上圖顯示出了計數排序的運行過程。
在第1~2行中的for循環初始化操作之後，在第3~4行檢查輸入的每一個元素。如果輸入元素的值為i，即增加C[i]的值。C[i]記錄了值為i的元素個數。
於是，在第4行之後C[i]中存放了等於i的元素的個數。在第6~7行中，通過數組C中記錄計數和，可以確定對每一個i=0,1,2.....,k,有多少輸入元素是小於等於i的。
最後，在第9~11行中的for循環部分，把每一個元素A[j]放在輸出數組B中與其相應的最終位置上。如果每一個元素都不相同，則當第一次執行第9行時，對每一個A[j]，值C[A[j]]即為A[j]在輸出數組上的最終位置上，因為共有C[A[j]]個元素小於等於A[j]。
可是由於各個元素可能不一定是不同的，因此，每當將一個值A[j]放入數組B中時，都要減小C[A[j]]額值。這會使得下一個值等於A[j]的輸入元素直接進入輸出數組B中A[j]的前一個位置。
四 代碼
/*********************************
*   日期：2014-04-26
*   作者：SJF0115
*   題目: 計數排序
**********************************/
#include <iostream>
#include <stdio.h>
using namespace std;


void COUNTINGSORT(int *A,int *B,int len,int k){
    if(A == NULL || k <= 0 || len <= 0){
        return;
    }
    int C[k+1],i;
    //初始化
    for(i = 0;i <= k;i++){
        C[i] = 0;
    }
    //統計值為A[i]的個數,C[i]是等於i的元素個數
    for(i = 0;i < len;i++){
        C[A[i]] ++;
    }
    //確定值A[i]在最終輸出數組B中位置,C[i]是小於等於i的元素個數
    for(i = 1;i <= k;i++){
        C[i] += C[i-1];
    }
    //輸出到數組B中
    for(i = len-1;i >= 0;i--){
        //index元素A[i]在數組B中的下標
        int index = C[A[i]];
        B[index] = A[i];
        //如果有相同值元素的情況
        C[A[i]] --;
    }
    //B下標從1開始
}

int main(){
    int A[8] = {2,5,3,0,2,3,0,3};
    int B[9];
    COUNTINGSORT(A,B,8,5);
    for(int i = 1;i <= 8;i++){
        printf("%d\n",B[i]);
    }
    return 0;
}


五 時間複雜度分析

時間複雜度是多少呢？
第1~2行for循環所花時間為Θ（k）。
第3~4行for循環所花時間為Θ（n）。
第6~7行for循環所花時間為Θ（k）。
第9~11行for循環所花時間為Θ（n）。
這樣總的時間就是Θ（k+n）。在實踐中，檔k = O（n）時，我們常采用計數排序，這時運行時間為Θ（n）。
六 特點

1.  提前必須是已知待排序的關鍵字為整型且範圍已知。

2.  時間複雜度為O(n+k)，不是基於比較的排序算法，因此效率非常之高。

3.  穩定性好，這個是計數排序非常重要的特性，可以用在後麵介紹的基數排序中。

4.  但需要一些輔助數組，如C[0..k]，因此待排序的關鍵字範圍0~k不宜過大。

最後更新：2017-04-03 12:56:25

  上一篇：go C讀寫配置文件
  下一篇：go 排錯公式-jobdu-1451