性時間排序-計數排序、基數排序和桶排序詳解與編程實現

計數排序

計數排序假設n個輸入元素中的每一個都是介於0到k之間的整數。此處k為某個整數（輸入數據在一個小范圍內）。

算法思想

計數排序的基本思想是對每一個輸入元素x，確定出小於x的元素的個數。然後再將x直接放置在它在最終輸出數組中的位置上。

由於數組中可能有相等的數，在處理時需要注意。

時間復雜度和空間復雜度分析

算法總時間Θ(k + n)。當k=O(n)時，計數排序的運行時間是Θ(n)。

空間復雜度是O(n+k)。需要兩個輔助數組：存放排序結果的數組B[n]，存放臨時結果的C[k]。

計數排序是穩定的排序算法。

編程實現（CPP）

[cpp] 
//計數排序-《算法導論（第二版）》P98 8.2計數排序  
//Author：江南煙雨  
//E-Mail：[email protected]  
 
#include <iostream>  
#include <cstdlib>  
 
using namespace std; 
 
void CountSort(int *a,const int num,int *result) 
{ 
    int MaxVal = -99999; 
    for(int i = 0;i < num;++i) 
    { 
        if(MaxVal < *(a + i)) 
            MaxVal = *(a + i); 
    } 
    int *tempResult = new int[MaxVal + 5];//記錄中間結果  
    for(int i = 0;i < MaxVal  + 5;++i) 
        *(tempResult + i) = 0; 
    //result[i]記錄數組中值等於i的元素的個數  
    for(int i = 0;i < num;++i) 
        *(tempResult + *(a + i)) = *(tempResult + *(a + i)) + 1; 
    //result[i]記錄數組中值小於等於i的元素的個數  
    for(int i = 1;i < MaxVal + 5;++i) 
        *(tempResult + i) = *(tempResult + i) + *(tempResult + i - 1); 
    //注意，數組中可能存在相等的元素  
    //將數組中各元素直接放入正確的位置  
    for (int i = num - 1;i >= 0;--i) 
    { 
        *(result + *(tempResult + *(a + i))) = *(a + i); 
        *(tempResult + *(a + i)) = *(tempResult + *(a + i)) - 1; 
    } 
 
    delete[] tempResult; 
} 
 
int main() 
{ 
     int num = 7; 
    int *a = new int[num]; 
    for(int i = 0;i < num;++i) 
        *(a + i) = rand(); 
 
    cout << "Before sort: " << endl; 
    for(int i = 0;i < num;++i) 
        cout << *(a + i) << " "; 
    cout << endl; 
 
    int *result = new int[num + 5]; 
 
    CountSort(a,num,result); 
 
    cout << "After sort: " << endl; 
    for(int i = 1;i <= num;++i) 
        cout << *(result + i) << " "; 
    cout << endl; 
 
    delete[] a; 
    delete[] result; 
} 

//計數排序-《算法導論（第二版）》P98 8.2計數排序
//Author：江南煙雨
//E-Mail：[email protected]

#include <iostream>
#include <cstdlib>

using namespace std;

void CountSort(int *a,const int num,int *result)
{
 int MaxVal = -99999;
 for(int i = 0;i < num;++i)
 {
  if(MaxVal < *(a + i))
   MaxVal = *(a + i);
 }
 int *tempResult = new int[MaxVal + 5];//記錄中間結果
 for(int i = 0;i < MaxVal  + 5;++i)
  *(tempResult + i) = 0;
 //result[i]記錄數組中值等於i的元素的個數
 for(int i = 0;i < num;++i)
  *(tempResult + *(a + i)) = *(tempResult + *(a + i)) + 1;
 //result[i]記錄數組中值小於等於i的元素的個數
 for(int i = 1;i < MaxVal + 5;++i)
  *(tempResult + i) = *(tempResult + i) + *(tempResult + i - 1);
 //注意，數組中可能存在相等的元素
 //將數組中各元素直接放入正確的位置
 for (int i = num - 1;i >= 0;--i)
 {
  *(result + *(tempResult + *(a + i))) = *(a + i);
  *(tempResult + *(a + i)) = *(tempResult + *(a + i)) - 1;
 }

 delete[] tempResult;
}

int main()
{
  int num = 7;
 int *a = new int[num];
 for(int i = 0;i < num;++i)
  *(a + i) = rand();

 cout << "Before sort: " << endl;
 for(int i = 0;i < num;++i)
  cout << *(a + i) << " ";
 cout << endl;

 int *result = new int[num + 5];

 CountSort(a,num,result);

 cout << "After sort: " << endl;
 for(int i = 1;i <= num;++i)
  cout << *(result + i) << " ";
 cout << endl;

 delete[] a;
 delete[] result;
}

基數排序

算法思想
基數排序是從低位到高位依次對所有的數進行排序。如果所有的數最高位數是d，那麼先按最低有效位數字進行排序，得到一個結果。然後往高位重復這個過程。

需要注意的是，按位排序必須是穩定的排序算法。經常采用的是計數排序。

編程實現（CPP）

[cpp]
//基數排序  
//《算法導論（第二版）》P100 8.3 基數排序  
//Author：江南煙雨  
//E-Mail:[email protected]  
 
#include <iostream>  
#include <cstdlib>  
#include <ctime>  
 
using namespace std; 
 
//得到某個整數第i位的數值  
int getDigitNun(int a,int digit); 
//按位排序  
void DigitSort(int *a,int n,int digit,int *result); 
//基數排序算法  
void RadixSort(int *a,int n,int d); 
 
int main() 
{ 
    int n = 7,i; 
    int *a = new int[n]; 
    srand(time(NULL)); 
    for(i = 0;i < n;++i) 
        *(a + i) = rand(); 
    //判斷最大的數的位數  
    int MaxVal = -1,d = 0; 
    cout << "Before sort : " << endl; 
    for(i = 0;i < n;++i) 
    { 
        cout << *(a + i) << " "; 
        MaxVal = MaxVal < *(a + i) ? *(a + i) : MaxVal; 
    } 
    cout << endl; 
    while(MaxVal > 0) 
    { 
        ++d; 
        MaxVal /= 10; 
    } 
 
    RadixSort(a,n,d); 
 
    cout << "After sort : " << endl; 
    for(i = 0;i < n;++i) 
        cout << *(a + i) << " "; 
    cout << endl; 
} 
 
//基數排序算法  
void RadixSort(int *a,int n,int d) 
{ 
    int *result = new int[n + 5]; 
    //循環執行按位排序操作  
    for (int i =1;i <= d;++i) 
    { 
        DigitSort(a,n,i,result); 
        for (int j = 0;j < n;++j) 
        { 
            *(a + j) = *(result + j + 1); 
        } 
    } 
 
    delete[] result; 
} 
 
//得到某個整數第i位的數值  
int getDigitNun(int a,int digit) 
{ 
    while(--digit) 
    { 
        a /= 10; 
    } 
 
    return a % 10; 
} 
 
//按位排序  
//這裡采用選擇排序  
void DigitSort(int *a,int n,int digit,int *result) 
{ 
    //記錄中間結果  
    const int num = 15; 
    int *tempResult = new int[num]; 
    for(int i = 0;i < num;++i) 
        *(tempResult + i) = 0;//初始化  
 
    //tempResult[i]記錄數組中等於i的數的個數  
    for(int i = 0;i < n;++i) 
        *(tempResult + getDigitNun(*(a + i),digit)) = *(tempResult + getDigitNun(*(a + i),digit)) + 1; 
 
    //tempResult[i]記錄數組中小於等於i的數的個數  
    for(int i = 1;i < num;++i) 
        *(tempResult + i) = *(tempResult + i) + *(tempResult + i - 1); 
 
    //將個元素直接放入正確的位置  
    for(int i = n - 1;i >= 0;--i) 
    { 
        *(result + *(tempResult + getDigitNun(*(a + i),digit))) = *(a + i); 
        *(tempResult + getDigitNun(*(a + i),digit)) = *(tempResult + getDigitNun(*(a + i),digit)) - 1; 
    } 
 
    delete[] tempResult; 
} 

//基數排序
//《算法導論（第二版）》P100 8.3 基數排序
//Author：江南煙雨
//E-Mail:[email protected]

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

//得到某個整數第i位的數值
int getDigitNun(int a,int digit);
//按位排序
void DigitSort(int *a,int n,int digit,int *result);
//基數排序算法
void RadixSort(int *a,int n,int d);

int main()
{
 int n = 7,i;
 int *a = new int[n];
 srand(time(NULL));
 for(i = 0;i < n;++i)
  *(a + i) = rand();
 //判斷最大的數的位數
 int MaxVal = -1,d = 0;
 cout << "Before sort : " << endl;
 for(i = 0;i < n;++i)
 {
  cout << *(a + i) << " ";
  MaxVal = MaxVal < *(a + i) ? *(a + i) : MaxVal;
 }
 cout << endl;
 while(MaxVal > 0)
 {
  ++d;
  MaxVal /= 10;
 }

 RadixSort(a,n,d);

 cout << "After sort : " << endl;
 for(i = 0;i < n;++i)
  cout << *(a + i) << " ";
 cout << endl;
}

//基數排序算法
void RadixSort(int *a,int n,int d)
{
 int *result = new int[n + 5];
 //循環執行按位排序操作
 for (int i =1;i <= d;++i)
 {
  DigitSort(a,n,i,result);
  for (int j = 0;j < n;++j)
  {
   *(a + j) = *(result + j + 1);
  }
 }

 delete[] result;
}

//得到某個整數第i位的數值
int getDigitNun(int a,int digit)
{
 while(--digit)
 {
  a /= 10;
 }

 return a % 10;
}

//按位排序
//這裡采用選擇排序
void DigitSort(int *a,int n,int digit,int *result)
{
 //記錄中間結果
 const int num = 15;
 int *tempResult = new int[num];
 for(int i = 0;i < num;++i)
  *(tempResult + i) = 0;//初始化

 //tempResult[i]記錄數組中等於i的數的個數
 for(int i = 0;i < n;++i)
  *(tempResult + getDigitNun(*(a + i),digit)) = *(tempResult + getDigitNun(*(a + i),digit)) + 1;

 //tempResult[i]記錄數組中小於等於i的數的個數
 for(int i = 1;i < num;++i)
  *(tempResult + i) = *(tempResult + i) + *(tempResult + i - 1);

 //將個元素直接放入正確的位置
 for(int i = n - 1;i >= 0;--i)
 {
  *(result + *(tempResult + getDigitNun(*(a + i),digit))) = *(a + i);
  *(tempResult + getDigitNun(*(a + i),digit)) = *(tempResult + getDigitNun(*(a + i),digit)) - 1;
 }

 delete[] tempResult;
}

時間復雜度和空間復雜度分析
給定n個d位數，每一個數位可能取值中數是k，如果所用的穩定的按位排序時間復雜度是Θ(n+k)，基數排序時間復雜度是Θ(d(n+k))。空間復雜度O(n+k)。

當d為常數，k=O(n)時，基數排序有線性時間復雜度。

關於如何將每個關鍵字分解成若干數位方面，有另外一個定理：

給定n個b維數和任何正整數r<=b，基數排序能在Θ((b/r)(n+2^r))時間內對這些數進行排序。

這裡，對一個值r<=b，將每個關鍵字看做是有d = floor(b/r)個數字，每個數字含有r位，再進行計數排序。

上述式子可以推導得到Θ(n)復雜度。

但是這並不意味著基數排序比基於比較的排序算法比如快排更好！因為隱含在記號中的常數因子是不同的。哪一個排序算法更好取決於底層機器的實現特性，比如快排同==排通常可以更有效地利用硬件緩存。同時還取決於輸入數據。而且利用計數排序作為中間穩定排序不是原地排序。

桶排序
當輸入數據符合均勻分布時，即可以以線性期望時間運行。即使輸入不滿足線性關系，桶排序也仍然可以以線性時間運行。只要輸入滿足這樣一個性質，即各個桶尺寸的平方和與總的元素數呈線性關系。

桶排序的思想：

將區間[0,1)分成n個相同大小的子區間，或稱為桶。然後將n個輸入元素分布到各個桶中去。每個桶中的元素用一個鏈表來存儲。

編程實現（CPP）

[cpp] 
//桶排序  
//《算法導論（第二版）》P102 8.4 桶排序  
//Author：江南煙雨（2013-03027）  
//E-Mail:[email protected]  
 
#include <iostream>  
#include <cstdlib>  
#include <ctime>  
#include <cmath>  
 
using namespace std; 
 
//桶中鏈表節點數據結構  
typedef struct StructLinkNode{ 
    double elem; 
    struct StructLinkNode *next; 
}LinkNode,*LinkNodePtr; 
 
//桶排序  
void BucketSort(double *a,int n); 
//刪除一條鏈表  
void deleteLinkList(LinkNodePtr head); 
 
int main() 
{ 
    srand(time(NULL)); 
    int n = 8; 
    double *a = new double[n]; 
    for(int i = 0;i < n;++i) 
        *(a + i) = rand() * 1.0 / RAND_MAX; 
 
    cout << "Before sort : " << endl; 
    for(int i = 0;i < n;++i) 
        cout << *(a + i) << "  "; 
    cout << endl; 
 
    BucketSort(a,n); 
 
    cout << "After sort : " << endl; 
    for(int i = 0;i < n;++i) 
        cout << *(a + i) << "  "; 
    cout << endl; 
} 
 
//桶排序  
void BucketSort(double *a,int n) 
{ 
    //存放鏈表的數組  
    LinkNodePtr *linkListArr = new LinkNodePtr[n]; 
    //初始化  
    for (int i = 0;i < n;++i) 
    { 
        linkListArr[i] = new LinkNode; 
        linkListArr[i]->elem = -1; 
        linkListArr[i]->next = NULL; 
    } 
 
    //將n個輸入元素依次放入n個桶中  
    for (int i = 0;i < n;++i) 
    { 
        LinkNodePtr newNode = new LinkNode; 
        newNode->elem = *(a + i); 
        newNode->next = NULL; 
 
        //將新元素插入對應桶的鏈表的正確位置  
        int index = floor(n * *(a + i)); 
        LinkNodePtr loopPtr = linkListArr[index]->next; 
        LinkNodePtr prevPtr = linkListArr[index]; 
        while(loopPtr != NULL && *(a + i) > loopPtr->elem) 
        { 
            prevPtr = loopPtr; 
            loopPtr = loopPtr->next; 
        } 
        newNode->next = loopPtr; 
        prevPtr->next = newNode; 
    } 
 
    int count = 0; 
    for (int i = 0;i < n;++i) 
    { 
        LinkNodePtr loopPtr = linkListArr[i]->next; 
        while(loopPtr != NULL) 
        { 
            *(a + count) = loopPtr->elem; 
            ++count; 
            loopPtr = loopPtr->next; 
        } 
    } 
 
    for (int i = 0;i < n;++i) 
        deleteLinkList(linkListArr[i]); 
} 
 
//刪除一條鏈表  
void deleteLinkList(LinkNodePtr head) 
{ 
    if (NULL == head) 
    { 
        return; 
    } 
    deleteLinkList(head->next); 
    delete head; 
} 

//桶排序
//《算法導論（第二版）》P102 8.4 桶排序
//Author：江南煙雨（2013-03027）
//E-Mail:[email protected]

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>

using namespace std;

//桶中鏈表節點數據結構
typedef struct StructLinkNode{
 double elem;
 struct StructLinkNode *next;
}LinkNode,*LinkNodePtr;

//桶排序
void BucketSort(double *a,int n);
//刪除一條鏈表
void deleteLinkList(LinkNodePtr head);

int main()
{
 srand(time(NULL));
 int n = 8;
 double *a = new double[n];
 for(int i = 0;i < n;++i)
  *(a + i) = rand() * 1.0 / RAND_MAX;

 cout << "Before sort : " << endl;
 for(int i = 0;i < n;++i)
  cout << *(a + i) << "  ";
 cout << endl;

 BucketSort(a,n);

 cout << "After sort : " << endl;
 for(int i = 0;i < n;++i)
  cout << *(a + i) << "  ";
 cout << endl;
}

//桶排序
void BucketSort(double *a,int n)
{
 //存放鏈表的數組
 LinkNodePtr *linkListArr = new LinkNodePtr[n];
 //初始化
 for (int i = 0;i < n;++i)
 {
  linkListArr[i] = new LinkNode;
  linkListArr[i]->elem = -1;
  linkListArr[i]->next = NULL;
 }

 //將n個輸入元素依次放入n個桶中
 for (int i = 0;i < n;++i)
 {
  LinkNodePtr newNode = new LinkNode;
  newNode->elem = *(a + i);
  newNode->next = NULL;

  //將新元素插入對應桶的鏈表的正確位置
  int index = floor(n * *(a + i));
  LinkNodePtr loopPtr = linkListArr[index]->next;
  LinkNodePtr prevPtr = linkListArr[index];
  while(loopPtr != NULL && *(a + i) > loopPtr->elem)
  {
   prevPtr = loopPtr;
   loopPtr = loopPtr->next;
  }
  newNode->next = loopPtr;
  prevPtr->next = newNode;
 }

 int count = 0;
 for (int i = 0;i < n;++i)
 {
  LinkNodePtr loopPtr = linkListArr[i]->next;
  while(loopPtr != NULL)
  {
   *(a + count) = loopPtr->elem;
   ++count;
   loopPtr = loopPtr->next;
  }
 }

 for (int i = 0;i < n;++i)
  deleteLinkList(linkListArr[i]);
}

//刪除一條鏈表
void deleteLinkList(LinkNodePtr head)
{
 if (NULL == head)
 {
  return;
 }
 deleteLinkList(head->next);
 delete head;
}

時間和空間復雜度分析

時間復雜度是O(n)。

空間復雜度是O(n)。需要一個輔助數組來存放桶（鏈表）。

即使輸入不滿足均勻分布，桶排序也仍然可以以線性時間運行，只要輸入滿足這樣一個條件：各個桶尺寸的平方和與總的元素呈線性關系。

桶排序是穩定排序算法。