計數(shù)排序

計數(shù)排序是一種高效的線性排序。

它通過計算一個集合中元素出現(xiàn)的次數(shù)來確定集合如何排序。不同于插入排序、快速排序等基于元素比較的排序，計數(shù)排序是不需要進行元素比較的，而且它的運行效率要比效率為O（nlgn）的比較排序高。

計數(shù)排序有一定的局限性，其中最大的局限就是它只能用于整型或那么可以用整型來表示的數(shù)據(jù)集合。原因是計數(shù)排序利用一個數(shù)據(jù)的索引來記錄元素出現(xiàn)的次數(shù)，而這個數(shù)組的索引就是元素的數(shù)值。例如，如果整數(shù)3出現(xiàn)過4次，那么4將存儲到數(shù)組索引為3的位置上。同時，我們還需要知道集合中最大整數(shù)的值，以便于為數(shù)組分配足夠的空間。

除了速度之外，計數(shù)排序的另一個優(yōu)點就是非常穩(wěn)定。穩(wěn)定的排序能使具有相同數(shù)值的元素具有相同的順序，就像它們在原始集合中表現(xiàn)出來的一樣。在某些情況下這是一個重要的特性，可以在基數(shù)排序中看到這一點。

計數(shù)排序的接口定義

ctsort

---

int ctsort(int *data, int size, int k);

返回值：如果排序成功，返回0；否則，返回-1；

描述： 利用計數(shù)排序?qū)?shù)組data中的整數(shù)進行排序。data中的元素個數(shù)由size決定。參數(shù)k為data中最大的整數(shù)加1。當(dāng)ctsort返回時，data中包含已經(jīng)排序的元素。

復(fù)雜度：O（n+k），n為要排序的元素個數(shù)，k為data中最大的整數(shù)加1。

計數(shù)排序的實現(xiàn)與分析

計數(shù)排序本質(zhì)上是通過計算無序集合中整數(shù)出現(xiàn)的次數(shù)來決定集合應(yīng)該如何排序的。

在以下說明的實現(xiàn)方法中，data初始包含size個無序整型元素，并存放在單塊連續(xù)的存儲空間中。另外需要分配存儲空間來臨時存放已經(jīng)排序的元素。在ctsort返回時，得到的有序集合將拷貝加data。

分配了存儲空間以后，首先計算data中每個元素出現(xiàn)的次數(shù)。這些結(jié)果將存儲到計數(shù)數(shù)組counts中，并且數(shù)組的索引值就是元素本身。一旦data中每個元素的出現(xiàn)次數(shù)都統(tǒng)計出來后，就要調(diào)整計數(shù)值，使元素在進入有序集合之前，清楚每個元素插入的次數(shù)。用元素本身的次數(shù)加上它前一個元素的次數(shù)。事實上，此時counts包含每個元素在有序集合temp中的偏移量。

要完成排序，還必須按照元素在temp中的偏移量放置元素。當(dāng)temp更新時，每個元素的計數(shù)要減1，這樣，在data中出現(xiàn)不止一次的元素在temp中也會出現(xiàn)不止一次，這樣保持同步。

計數(shù)排序的時間復(fù)雜度為O（n+k），其中n為要排序的元素個數(shù)，k為data中最大的整數(shù)加1。這是由于計數(shù)排序包含三個循環(huán)，其中兩個的運行時間正比于n，另一個的運行時間正比于k。對于空間上來說，計數(shù)排序需要兩個大小為n的數(shù)組，一個大小為k的數(shù)組。

示例：計數(shù)排序的實現(xiàn)

/*ctsort.c*/
#include <stdlib.h>
#include <string.h>
#include "sort.h"

/*ctsort  計數(shù)排序函數(shù)*/
int ctsort(int *data, int size, int k)
{
    int *counts,
        *temp;
        
    int i,j;
    
    /*為計數(shù)器數(shù)組分配空間*/
    if((counts = (int *)malloc(k * sizeof(int))) == NULL)
        return -1;
    
    /*為已排序元素臨時存放數(shù)組分配空間*/
    if((temp = (int *)malloc(size * sizeof(int))) == NULL)
        return -1;
    
    /*初始化計數(shù)數(shù)組*/
    for(i = 0; i < k; i++)
    {
        counts[i] = 0;        
    }
    
    /*統(tǒng)計每個元素出現(xiàn)的次數(shù)（counts的下標索引即是要統(tǒng)計的元素本身）*/
    for(j=0; j<size; j++)
        counts[data[j]]=counts[data[j]] + 1;
    
    /*將元素本身的次數(shù)加上它前一個元素的次數(shù)(得到元素偏移量)*/
    for(i = 1; i < k; i++)
        counts[i]=counts[i] + counts[i-1];
    
    /*關(guān)鍵代碼：使用上面得到的計數(shù)數(shù)組去放置每個元素要排序的位置*/
    for(j = size -1; j >= 0; j--)
    {
        temp[counts[data[j]]-1] = data[j];      /*counts的值是元素要放置到temp中的偏移量*/
        counts[data[j]] = counts[data[j]] - 1;  /*counts的計數(shù)減1*/
    }
    
    /*將ctsort已排序的元素從temp拷貝回data*/
    memcpy(data,temp,size * sizeof(int));
    
    /*釋放前面分配的空間*/
    free(counts);
    free(temp);
    
    return 0;
}

基數(shù)排序

基數(shù)排序是另外一種高效的線性排序算法。

其方法是將數(shù)據(jù)按位分開，并從數(shù)據(jù)的最低有效位到最高有效位進行比較，依次排序，從而得到有序數(shù)據(jù)集合。

我們來看一個例子，用基數(shù)排序?qū)κM制數(shù)據(jù){15，12，49，16，36，40}進行排序。在對個位進行排序之后，其結(jié)果為{40，12，15，16，36，49}，在對十位進行排序之后，其結(jié)果為{12，15，16，36，40，49}。

有一點非常重要，在對每一位進行排序時其排序過程必須是穩(wěn)定的。一旦一個數(shù)值通過較低有效位的值進行排序之后，此數(shù)據(jù)的位置不應(yīng)該改變，除非通過較高有效位的值進行比較后需要調(diào)整它的位置。例如，在上述的例子中，12和15的十位都是1，當(dāng)對其十位進行排序時，一個不穩(wěn)定的排序算法可能不會維持其在個數(shù)排序過程中的順序。而一個穩(wěn)定的排序算法可以保證它們不重新排序。基數(shù)排序會用到計數(shù)排序，對于基數(shù)排序來說，除了穩(wěn)定性，它還是一種線性算法，且必須知道每一位可能的最大整數(shù)值。

基數(shù)排序并不局限于對整數(shù)進行排序，只要能把元素分割成整型數(shù)，就可以使用基數(shù)排序。例如，可以對一個以2⁸為基數(shù)字符串進行基數(shù)排序；或者，可以對一個64位的整數(shù)，按4位以2¹⁶為基數(shù)的值進行排序。具體該選擇什么值作為基數(shù)取決于數(shù)據(jù)本身，同時考慮到空間的限制，需要將pn+pk最小化。（其中p為每個元素的位數(shù)，n為元素的個數(shù)，k為基數(shù)）。一般情況下，通常使k小于等于n。

基數(shù)排序的接口定義

rxsort

---

int rxsort(int *data, int size, int p, int k);

返回值：如果排序成功，返回0；否則返回-1。

描述：利用計數(shù)排序?qū)?shù)組data中的整數(shù)進行排序。數(shù)組data中整數(shù)的個數(shù)由size決定。參數(shù)p指定每個整數(shù)包含的位數(shù)，k指定基數(shù)。當(dāng)rxsort返回時，data包含已經(jīng)排序的整數(shù)。

復(fù)雜度：O（pn+pk），n為要排序的元素個數(shù)，k為基數(shù)，p為位的個數(shù)。

基數(shù)排序的實現(xiàn)與分析

基數(shù)排序?qū)嵸|(zhì)上是在元素每一位上應(yīng)用計數(shù)排序來對數(shù)據(jù)集合排序。在以下介紹的實現(xiàn)方法中，data初始包含size個無序整型元素，并存放在單塊連續(xù)的存儲空間中。當(dāng)rxsort返回時，data中的數(shù)據(jù)集完全有序。

如果我們理解了計數(shù)排序的方法，那么基數(shù)排序也就非常簡單了。單個循環(huán)控制正在進行排序的位置。從最低位開始一個位置一個位置地應(yīng)用計數(shù)排序來不斷調(diào)整元素。一旦調(diào)整完了最高有效位的數(shù)值，排序過程就完成了。

獲取每位數(shù)值的簡單方法就是使用冪運算和模運算。這對整數(shù)來說特別有效，但不同的數(shù)據(jù)類型需要使用不同的方法。有一些方法可能需要考慮機器具體細節(jié)，例如字節(jié)順序和字對齊等。

毫無疑問，基數(shù)排序的時間復(fù)雜度取決于它選擇哪種穩(wěn)定排序來對數(shù)值進行排序。由于基數(shù)排序?qū)γ總€p位置的位數(shù)值使用計數(shù)排序，因此基數(shù)排序消耗的運行時間是計數(shù)排序的p倍，即O（pn+pk）。其對空間的要求與計數(shù)排序一樣：兩個大小為n的數(shù)組，一個大小為k的數(shù)組。

示例：基數(shù)排序的實現(xiàn)

/*rxsort.c*/
#include <limits.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>

#include "sort.h"

/*rxsort*/
int rxsort(int *data, int size, int p, int k)
{
    int *counts, *temp;
    int index, pval, i, j, n;
    
    /*為計數(shù)器數(shù)組分配空間*/
    if((counts = (int *)malloc(k * sizeof(int))) == NULL)
        return -1;
    /*為已排序元素集分配空間*/
    if((temp = (int *)malloc(size * sizeof(int))) == NULL)
        return -1;
    
    /*從元素的最低位到最高位開始排序*/
    for(n=0; n<p; n++)
    {
        /*初始化計數(shù)器*/
        for(i=0; i<k; i++)
            count[i] = 0;
        /*計算位置值（冪運算k的n次方）*/
        pval = (int)pow((double)k,(double)n);
        
        /*統(tǒng)計當(dāng)前位上每個數(shù)值出現(xiàn)的次數(shù)*/
        for(j=0; j<size; j++)
        {
            index = (int)(data[j] / pval) % k;
            counts[index] = counts[index]+1;
        }
        /*計算偏移量（本身的次數(shù)加上前一個元素次數(shù)）*/
        for(i=1; i<k; i++)
            counts[i] = counts[i] + counts[i-1];
        
        /*使用計數(shù)器放置元素位置*/
        for(j=size-1; j>=0; j--)
        {
            index = (int)(data[j] / pval) % k;
            temp[counts[index]-1] = data[j];
            counts[index] = counts[index] - 1;
        }
        
        /*將已排序元素拷貝回data*/
        memcpy(data, temp, size*sizeof(int));
        
    }
    
    /*釋放已排序空間*/
    free(counts);
    free(temp);
    
    return 0;
}

總結(jié)

以上是生活随笔為你收集整理的排序算法的C语言实现(下 线性时间排序：计数排序与基数排序)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。