C++實(shí)現(xiàn)位圖排序?qū)嵗?/h1>

來(lái)源：本站原創(chuàng)|時(shí)間：2020-01-10|欄目：C語(yǔ)言|點(diǎn)擊： 次

在《編程珠璣》一書里提到了一種算法導(dǎo)論里沒有提到過的位圖排序方法，這種排序方法是通過犧牲空間效率來(lái)追求時(shí)間效率（線性時(shí)間）以達(dá)到時(shí)間-空間折中與雙贏的目的。本文以實(shí)例形式簡(jiǎn)單講一下位圖排序思想。

一、問題描述

     1.輸入：一個(gè)至多包含1千萬(wàn)個(gè)非負(fù)整數(shù)的文件

     2.特征：①每個(gè)數(shù)都是小于10000000的非負(fù)整數(shù)；②沒有重復(fù)的數(shù)字；③數(shù)據(jù)之間不存在關(guān)聯(lián)關(guān)系。

     3.約束：①最多1MB的內(nèi)存空間可用；②磁盤空間充足；③運(yùn)行時(shí)間最多幾分鐘，最好是線性時(shí)間。
    
     4.輸出：按升序排列的整數(shù)序列。

二、位圖排序思想

由于待排序的數(shù)據(jù)記錄較多，我們單純地使用常見的排序方法時(shí)間效率較低，運(yùn)行時(shí)間會(huì)很長(zhǎng)。而且內(nèi)存空間有限（限制為1MB左右），所以我們不能同時(shí)把所有整數(shù)讀入內(nèi)存（如果每個(gè)整數(shù)使用7個(gè)字節(jié)來(lái)存儲(chǔ)，那么1MB內(nèi)存空間只能存大約143000個(gè)數(shù)字）。當(dāng)然我們可以多次讀取輸入文件，多次排序，但是更好的方案是使用位圖排序，可以使用有限的1MB內(nèi)存空間并只進(jìn)行一趟排序。

1.根據(jù)待排序集合中最大的數(shù)，開辟一個(gè)位數(shù)組，用來(lái)表示待排序集合中的整數(shù)；

2.待排序集合中的數(shù)字在位數(shù)組中的對(duì)應(yīng)位置置1，其他的置0；

例如，待排序集合{1,2,3,5,8,13}可以表示為：0-1-1-1-0-1-0-0-1-0-0-0-0-1

這樣排序過程自然可以分為三步：

第一步：將所有的位都置為0；

第二步：通過讀入文件中的每個(gè)整數(shù)，將每個(gè)對(duì)應(yīng)的位都置為1；

第三步：檢驗(yàn)每一位，如果該位為1，輸出對(duì)應(yīng)的整數(shù)。

注意：位圖排序是使用一個(gè)二進(jìn)制位而不是一個(gè)整數(shù)來(lái)表示0或1，這樣可以大大地減少所需要的內(nèi)存空間。使用位圖排序的前提是要知道待排序序列中的最大數(shù)。位圖排序的缺點(diǎn)是有些數(shù)沒有出現(xiàn)過，仍要為其保留一個(gè)位。故位圖排序比較適合關(guān)鍵字密集的序列，例如一個(gè)城市的電話號(hào)碼。

偽代碼如下：

/*Phase 1: initialize set to empty*/ 
  for i = [0, n) 
    bit[i] = 0 
/*Phase 2: insert present elements into the set*/ 
  for each i in the input file 
    bit[i] = 1 
/*Phase 3: write sorted output*/ 
  for i = [0, n) 
    if bit[i] == 1 
      write i on the output file 

性能：時(shí)間復(fù)雜度可達(dá)O(n)，1MB包含8*1024*1024個(gè)位，所需內(nèi)存10000000/(8*1024*1024)=1.20MB，如果不是嚴(yán)格限制的話可以看做基本符合要求。

三、位圖排序?qū)崿F(xiàn)

位圖排序時(shí)，我們需要考慮：給出一個(gè)數(shù)，如何找到其對(duì)應(yīng)位圖的位置，方法就是首先找到該數(shù)對(duì)應(yīng)的字節(jié)，然后在找到該數(shù)對(duì)應(yīng)的位。例如：

unsigned char bitmap[2]; 
/* 可以表示16個(gè)數(shù)，即0～15 */ 

一個(gè)字節(jié)有八位，5表示第0個(gè)字節(jié)的第5位上；14表示第1個(gè)字節(jié)的第6個(gè)位上。

在這里為了簡(jiǎn)化位處理，我們使用C++標(biāo)準(zhǔn)庫(kù)的bitset容器。bitset是C++提供的一種位集合的數(shù)據(jù)結(jié)構(gòu)，它讓我們可以像使用數(shù)組一樣使用位，可以訪問指定下標(biāo)的bit位。和其他容器一樣，bitset也是一個(gè)模板類。具體的bitset方法可以查看std::bitset reference。

下面我們使用bitset容器進(jìn)行位圖排序：

/************************************************************************* 
  > File Name: BitSort.cpp 
  > Author: SongLee 
 ************************************************************************/ 
#include<bitset> 
#include<iostream> 
using namespace std; 
 
#define MAX 20 
 
int main() 
{ 
  int arr[10] = {5,1,2,13,7,10,0,20,16,9}; 
 
  bitset<MAX+1> bit; 
   
  /* 將對(duì)應(yīng)位置置1 */ 
  for(int i=0; i<10; ++i) 
  { 
    bit.set(arr[i]); 
    /* bit.set(n)表示將第n位置1 */ 
  } 
 
  /* 輸出排序結(jié)果 */ 
  for(int i=0; i<MAX+1; ++i) 
  { 
    /* bit.test(n)判斷第n位是否為1 */ 
    if(bit.test(i)) 
    { 
      cout << i << " "; 
    } 
  } 
  cout << endl; 
} 

輸出結(jié)果：0 1 2 5 7 9 10 13 16 20