首页 > 代码库 > 桶排序--小试牛刀

桶排序--小试牛刀

2024-07-07 16:31:02   231人阅读

桶排序特点：

在桶的大小和元素个数呈现线性关系的时候，复杂度是线性的，最差是O（n^2）(个人理解是当所有元素都在一个桶的时候，采用插入排序的时候)；

稳定排序（注意实现的时候：对同一个桶内元素的排序要使用稳定排序实现）；

空间复杂度比较高；

 

桶排序的描述：

（1）初始化桶，将元素放入到合适的桶内

（2）对各个桶内的元素进行排序（插入排序）

（3）输出元素

具体流程就不介绍了，以下是个人的实现，主要分存在重复和不存在重复两种情况，我的代码只是测试，另外排序不是用的插入排序

 1 #include <iostream>
 2 #include <queue>
 3 #include <climits>
 4 #include <algorithm>
 5 #include <memory.h>
 6 #include <stdio.h>
 7 #include <ostream>
 8 #include <vector>
 9 #include <list>
10 
11 using namespace std;
12 
13 vector<int> data;
14 int maxNum = 99;
15 void bucket_sort_unique()
16 {
17     int *bucket = new int[100];
18     memset(bucket,-1,sizeof(bucket));
19     vector<int>::iterator it;
20     for(it = data.begin() ; it!=data.end() ; ++it)
21     {
22         bucket[*it] = *it;
23     }
24     for(int i = 0 ; i<100 ; ++i)
25     {
26         if(bucket[i] > 0)
27             cout<<" "<<bucket[i];
28     }
29 }
30 
31 void bucket_sort()
32 {
33     vector<list<int> > bucket(100);
34     vector<int>::iterator it;
35     it = data.begin();
36     while(it != data.end())
37     {
38         bucket[*it].push_back(*it);
39         ++it;
40     }
41     for(int i = 0 ; i<100 ; ++i)
42     {
43         if(bucket[i].size() != 0)
44         {
45             bucket[i].sort();
46             list<int>::iterator it1 = bucket[i].begin();
47             while(it1 != bucket[i].end())
48             {
49                 cout<<" "<<*it1;
50                 it1++;
51             }
52         }
53     }
54 }
55 
56 int main()
57 {
58     int n;
59     cin>>n;
60     while(n--)
61     {
62         int tmp;
63         cin>>tmp;
64         data.push_back(tmp);
65     }
66     //bucket_sort_unique();
67     bucket_sort();
68     return 0;
69 }

 


联系
我们