基數排序、桶排序
這里介紹一下非比較排序
頭緒比較亂
編程珠璣 I 第一節中就講到一種排序方法：大批量的數排序，內存有限，利用 bitmap 可以很好的解決。時間為 O(N) 。
對于不重復出現的數的集合，也就是說對于某個數最多只出現一次。可以利用 bitmap 來解決。因為一個 bit 只有兩個狀態： 0 和 1 。
1.
對于重復出現的數，可以利用一般類型數組來解決。對于每個數，以每個數為索引，記錄以該索引的元素自加 1 。處理完后，掃描這個輔助數組，將記錄的信息，也就是索引的次數，把索引以次數存入原來數組中。
2.
這種直接以待排序的數為索引，需要很大的輔助數組。所以可以利用針對待排序的數的每位來處理，每個位的范圍也就是 0 - 9 十的大小。對于多維的待排序數處理方式有兩種。即從左到右和從右到左。
從左到右：左面的排完序后，整體次序不變了，只是調整的次位的相對順序。
從右到左：右面的排完序后，整體的次序還會有變化的，只不過是隨著從右到左，依次調整的次數越來越少了。
3.
桶排序，對于一系列待排序數，可以先按照各個數的屬性將所有數分配到各個桶里。這樣后，對于每個桶里的數可以使用插入排序進行各個桶的排序。
1 #include <iostream>
2 #include <vector>
3 #include <cstring>
4 using namespace std;
5
6 void sort(vector<int>& array)
7 {
8 int temp[1000];
9 memset(temp, 0, sizeof (int) * 1000);
10 for (vector<int>::size_type i = 0; i != array.size(); ++i)
11 {
12 ++temp[array[i]];
13 }
14 array.clear();
15 for (int i = 0; i < 1000; ++i)
16 {
17 while (temp[i]-- != 0)
18 {
19 array.push_back(i);
20 }
21 }
22 }
23
24 int main()
25 {
26 vector<int> array;
27 for (int i = 0; i < 10; ++i)
28 {
29 array.push_back(i);
30 }
31 for (int i = 10; i >= 0; --i)
32 {
33 array.push_back(i);
34 }
35 sort(array);
36 for (vector<int>::size_type i = 0; i < array.size(); ++i)
37 {
38 cout << array[i] << ' ';
39 }
40 cout << endl;
41 return 0;
42 }
posted on 2011-06-21 22:45
unixfy 閱讀(376)
評論(0) 編輯 收藏 引用