快捷導(dǎo)航

C++線性時間的排序算法分析

更新時間：2014年08月14日 11:27:22 投稿：shichen2014

這篇文章主要介紹了C++線性時間的排序算法分析,是非常經(jīng)典的非比較排序算法,對于C++程序員有很大的借鑒價值,需要的朋友可以參考下

前面的文章已經(jīng)介紹了幾種排序算法，如插入排序（直接插入排序，折半插入排序，希爾排序）、交換排序（冒泡排序，快速排序）、選擇排序（簡單選擇排序，堆排序）、2-路歸并排序（可以參考前一篇文章：各種內(nèi)部排序算法的實現(xiàn)）等，這些排序算法都有一個共同的特點，就是基于比較。

本文將介紹三種非比較的排序算法：計數(shù)排序，基數(shù)排序，桶排序。它們將突破比較排序的Ω(nlgn)下界，以線性時間運行。

一、比較排序算法的時間下界

所謂的比較排序是指通過比較來決定元素間的相對次序。

“定理：對于含n個元素的一個輸入序列，任何比較排序算法在最壞情況下，都需要做Ω(nlgn)次比較。”
也就是說，比較排序算法的運行速度不會快于nlgn，這就是基于比較的排序算法的時間下界。

通過決策樹（Decision-Tree）可以證明這個定理，關(guān)于決策樹的定義以及證明過程在這里就不贅述了。讀者可以自己去查找資料，這里推薦大家看一看麻省理工學(xué)院公開課：算法導(dǎo)論的《MIT公開課：線性時間排序》。

根據(jù)上面的定理，我們知道任何比較排序算法的運行時間不會快于nlgn。那么我們是否可以突破這個限制呢？當(dāng)然可以，接下來我們將介紹三種線性時間的排序算法，它們都不是通過比較來排序的，因此，下界Ω(nlgn)對它們不適用。

二、計數(shù)排序（Counting Sort）

計數(shù)排序的基本思想就是對每一個輸入元素x，確定小于x的元素的個數(shù)，這樣就可以把x直接放在它在最終輸出數(shù)組的位置上，例如：

算法的步驟大致如下：

①.找出待排序的數(shù)組中最大和最小的元素

②.統(tǒng)計數(shù)組中每個值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項

③.對所有的計數(shù)累加（從C中的第一個元素開始，每一項和前一項相加）

④.反向填充目標(biāo)數(shù)組：將每個元素i放在新數(shù)組的第C(i)項，每放一個元素就將C(i)減去1

C++代碼如下：

/************************************************************************* 
  > File Name: CountingSort.cpp 
  > Author: SongLee 
 ************************************************************************/ 
#include<iostream> 
using namespace std; 
 
/* 
 *計數(shù)排序：A和B為待排和目標(biāo)數(shù)組，k為數(shù)組中最大值,len為數(shù)組長度 
 */ 
void CountingSort(int A[], int B[], int k, int len) 
{ 
  int C[k+1]; 
  for(int i=0; i<k+1; ++i) 
    C[i] = 0; 
  for(int i=0; i<len; ++i) 
    C[A[i]] += 1; 
  for(int i=1; i<k+1; ++i) 
    C[i] = C[i] + C[i-1]; 
  for(int i=len-1; i>=0; --i) 
  { 
    B[C[A[i]]-1] = A[i]; 
    C[A[i]] -= 1; 
  } 
} 
 
/* 輸出數(shù)組 */ 
void print(int arr[], int len) 
{ 
  for(int i=0; i<len; ++i) 
    cout << arr[i] << " "; 
  cout << endl; 
} 
 
/* 測試 */ 
int main() 
{ 
  int origin[8] = {4,5,3,0,2,1,15,6}; 
  int result[8]; 
  print(origin, 8); 
  CountingSort(origin, result, 15, 8); 
  print(result, 8); 
  return 0; 
}

當(dāng)輸入的元素是0到k之間的整數(shù)時，時間復(fù)雜度是O(n+k)，空間復(fù)雜度也是O(n+k)。當(dāng)k不是很大并且序列比較集中時，計數(shù)排序是一個很有效的排序算法。計數(shù)排序是一個穩(wěn)定的排序算法。

可能你會發(fā)現(xiàn)，計數(shù)排序似乎饒了點彎子，比如當(dāng)我們剛剛統(tǒng)計出C，C[i]可以表示A中值為i的元素的個數(shù)，此時我們直接順序地掃描C，就可以求出排序后的結(jié)果。的確是這樣，不過這種方法不再是計數(shù)排序，而是桶排序，確切地說，是桶排序的一種特殊情況。

三、桶排序（Bucket Sort）

桶排序（Bucket Sort）的思想是將數(shù)組分到有限數(shù)量的桶子里。每個桶子再個別排序（有可能再使用別的排序算法）。當(dāng)要被排序的數(shù)組內(nèi)的數(shù)值是均勻分配的時候，桶排序可以以線性時間運行。桶排序過程動畫演示：Bucket Sort，桶排序原理圖如下：

C++代碼如下：

/************************************************************************* 
  > File Name: BucketSort.cpp 
  > Author: SongLee 
 ************************************************************************/ 
#include<iostream> 
using namespace std; 
 
/* 節(jié)點 */ 
struct node 
{ 
  int value; 
  node* next; 
}; 
 
/* 桶排序 */ 
void BucketSort(int A[], int max, int len) 
{ 
  node bucket[len]; 
  int count=0; 
  for(int i=0; i<len; ++i) 
  { 
    bucket[i].value = 0; 
    bucket[i].next = NULL; 
  } 
   
  for(int i=0; i<len; ++i) 
  { 
    node *ist = new node(); 
    ist->value = A[i]; 
    ist->next = NULL; 
    int idx = A[i]*len/(max+1); // 計算索引 
    if(bucket[idx].next == NULL) 
    { 
      bucket[idx].next = ist; 
    } 
    else /* 按大小順序插入鏈表相應(yīng)位置 */ 
    { 
      node *p = &bucket[idx]; 
      node *q = p->next; 
      while(q!=NULL && q->value <= A[i]) 
      { 
        p = q; 
        q = p->next; 
      } 
      ist->next = q; 
      p->next = ist; 
    } 
  } 
 
  for(int i=0; i<len; ++i) 
  { 
    node *p = bucket[i].next; 
    if(p == NULL) 
      continue; 
    while(p!= NULL) 
    { 
      A[count++] = p->value; 
      p = p->next; 
    } 
  } 
} 
 
/* 輸出數(shù)組 */ 
void print(int A[], int len) 
{ 
  for(int i=0; i<len; ++i) 
    cout << A[i] << " "; 
  cout << endl; 
} 
 
/* 測試 */ 
int main() 
{ 
  int row[11] = {24,37,44,12,89,93,77,61,58,3,100}; 
  print(row, 11); 
  BucketSort(row, 235, 11); 
  print(row, 11); 
  return 0; 
}

四、基數(shù)排序（Radix Sort）

基數(shù)排序（Radix Sort）是一種非比較型排序算法，它將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個位分別進(jìn)行排序?；鶖?shù)排序的方式可以采用MSD（Most significant digital）或LSD（Least significant digital），MSD是從最高有效位開始排序，而LSD是從最低有效位開始排序。

當(dāng)然我們可以采用MSD方式排序，按最高有效位進(jìn)行排序，將最高有效位相同的放到一堆，然后再按下一個有效位對每個堆中的數(shù)遞歸地排序，最后再將結(jié)果合并起來。但是，這樣會產(chǎn)生很多中間堆。所以，通常基數(shù)排序采用的是LSD方式。

LSD基數(shù)排序?qū)崿F(xiàn)的基本思路是將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長度，數(shù)位較短的數(shù)前面補零。然后，從最低位開始，依次進(jìn)行一次排序。這樣從最低位排序一直到最高位排序完成以后, 數(shù)列就變成一個有序序列。需要注意的是，對每一個數(shù)位進(jìn)行排序的算法必須是穩(wěn)定的，否則就會取消前一次排序的結(jié)果。通常我們使用計數(shù)排序或者桶排序作為基數(shù)排序的輔助算法。基數(shù)排序過程動畫演示：Radix Sort

C++實現(xiàn)（使用計數(shù)排序）如下：

/************************************************************************* 
  > File Name: RadixSort.cpp 
  > Author: SongLee 
 ************************************************************************/ 
#include<iostream> 
using namespace std; 
 
// 找出整數(shù)num第n位的數(shù)字 
int findIt(int num, int n) 
{ 
  int power = 1; 
  for (int i = 0; i < n; i++) 
  { 
    power *= 10; 
  } 
  return (num % power) * 10 / power; 
} 
 
// 基數(shù)排序（使用計數(shù)排序作為輔助） 
void RadixSort(int A[], int len, int k) 
{ 
  for(int i=1; i<=k; ++i) 
  { 
    int C[10] = {0};  // 計數(shù)數(shù)組 
    int B[len];    // 結(jié)果數(shù)組 
 
    for(int j=0; j<len; ++j) 
    { 
      int d = findIt(A[j], i); 
      C[d] += 1; 
    } 
 
    for(int j=1; j<10; ++j) 
      C[j] = C[j] + C[j-1]; 
 
    for(int j=len-1; j>=0; --j) 
    { 
      int d = findIt(A[j], i); 
      C[d] -= 1; 
      B[C[d]] = A[j]; 
    } 
     
    // 將B中排好序的拷貝到A中 
    for(int j=0; j<len; ++j) 
      A[j] = B[j]; 
  } 
} 
 
// 輸出數(shù)組 
void print(int A[], int len) 
{ 
  for(int i=0; i<len; ++i) 
    cout << A[i] << " "; 
  cout << endl; 
} 
 
// 測試 
int main() 
{ 
  int A[8] = {332, 653, 632, 5, 755, 433, 722, 48}; 
  print(A, 8); 
  RadixSort(A, 8, 3); 
  print(A, 8); 
  return 0; 
}

基數(shù)排序的時間復(fù)雜度是 O(k·n)，其中n是排序元素個數(shù)，k是數(shù)字位數(shù)。注意這不是說這個時間復(fù)雜度一定優(yōu)于O(nlgn)，因為n可能具有比較大的系數(shù)k。

另外，基數(shù)排序不僅可以對整數(shù)排序，也可以對有多個關(guān)鍵字域的記錄進(jìn)行排序。例如，根據(jù)三個關(guān)鍵字年、月、日來對日期進(jìn)行排序。

您可能感興趣的文章: