位向量排序

當條件要求：

1.輸入數據限制在相對較小的範圍內;

2.數據沒有重複;

3.除了單一整數外,沒有任何其他關聯數據。這時，要完成這些數據的排序，簡單有效的方式就是進行為向量排序。

具體實現分為三個階段：a.將所有位都置為0，進行初始化；b.通過讀入檔案中的每個數據來建立集合，將每個對應的為都置為1；c.檢驗每一位，如果該位為1就將對應的整數輸出。至此，排序完成。C++實現具體步驟如下：

[cpp]

int main(void)

{

int i;

for(i = 0;i < N;i++)

clr(i);//復位整個數組

while(scanf("%d",&i) != EOF)

set(i);//把將要排序的數在數組中用位向量標記

for(i = 0;i < N;i++)

if(test(i))//用於比較i是否在數組中標記，若有標記就可以按順序輸出

printf("%d\n",i);

return 0;

}

N為需要排序的整數的可能最大值，clr函式將整個數組復位，然後set函式就是利用位向量的表示法將想排序的整數在數組中做一個標記；

當我們遍歷0～N的整數的時候，需要排序的整數肯定在這N個數裡面，只要利用test函式檢測i是否在數組中標記，就可以知道此數是否為我們要排序的數，如果有標記，直接輸出即可，這樣就可以達到排序的目的了；

該算法

時間複雜度：O(N)；空間複雜度：O(N/32 + 1)；