「データ構造とアルゴリズム分析:C言語記述」復習——第六章「ソート」——バケツソート

2014.06.17 06:22
概要:
バケツソートは非比較ソートであり,場合によってはO(n)に達する最良の複雑さがある.ソートアルゴリズムとしてあまり使われていないが,バケツの考え方はハッシュテーブルの鍵の一つである.
説明:
もし私たちがk個のバケツを持っていたら、0~k-1番です.では、ある根拠で配列のn個の要素をこのk個のバケツに割り当てます.そして各バケツを別々に並べ替えます.このk個のバケツは1つの条件を満たさなければならない.i個目のバケツはi+1個目のバケツより小さい.これらのバケツは、O(n)の時間を通じてすべての要素をバケツから取り出してつなぎ合わせ、配列された配列を得るために、ある順序を満たさなければならない.要素をバケツに割り当てる根拠は,ハッシュ関数と見なすことができる.バケツ内部のソートでは、他のソートアルゴリズムを使用できます.再帰的にバケツで並べ替えることもできますが、このような明らかな空間オーバーヘッドがあるアルゴリズムは、再帰的にはよくありません.
実装:

 1 // My implementation for radix sort.
 2 #include 
 3 #include 
 4 #include 
 5 using namespace std;
 6 
 7 void bucketSort(vector<int> &v)
 8 {
 9     const int BUCKET_SIZE = 1000;
10     const int BUCKET_NUM = 1000;
11     vector<int> buckets[BUCKET_NUM];
12     
13     int n, i, j, k;
14     
15     n = (int)v.size();
16     for (i = 0; i < n; ++i) {
17         buckets[v[i] / BUCKET_SIZE % BUCKET_NUM].push_back(v[i]);
18     }
19     
20     k = 0;
21     for (i = 0; i < BUCKET_NUM; ++i) {
22         if (buckets[i].size() > 1) {
23             sort(buckets[i].begin(), buckets[i].end());
24         }
25         for (j = 0; j < (int)buckets[i].size(); ++j) {
26             v[k++] = buckets[i][j];
27         }
28         buckets[i].clear();
29     }
30 }
31 
32 int main()
33 {
34     vector<int> v;
35     int n, i;
36     
37     while (cin >> n && n > 0) {
38         v.resize(n);
39         for (i = 0; i < n; ++i) {
40             cin >> v[i];
41         }
42         bucketSort(v);
43         for (i = 0; i < n; ++i) {
44             cout << v[i] << ' ';
45         }
46         cout << endl;
47     }
48     
49     return 0;
50 }

 
転載先:https://www.cnblogs.com/zhuli19901106/p/3792088.html