计数排序

计数排序实现:以学生年龄对学生信息进行排序。
 1 #include <iostream>
 2 #include <vector>
 3 #include <string>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 typedef struct StudentInfo 
 8 {
 9     unsigned int age;
10     string name;
11     string major;
12 }StudentInfo;
13 
14 struct StudentCount 
15 {
16     void operator()(StudentInfo stuInfo)
17     {
18         cout << stuInfo.name << " " << stuInfo.age << stuInfo.major << endl;
19     }
20 }student;
21 
22 void Countsort(vector<StudentInfo> &vec, unsigned int nMaxAge)
23 {
24     unsigned int* nCount = (unsigned int*)malloc(sizeof(unsigned int)*nMaxAge);
25     //vector<unsigned int> nCount(nMaxAge, 0);
26     memset(nCount, 0sizeof(unsigned int)*nMaxAge); //assign 0 to the array nCount
27     vector<StudentInfo>::const_iterator iter = vec.begin();
28     
29     //count the number of each age
30     for (; iter != vec.end(); ++iter) //用for_each试一下
31     {
32         ++nCount[iter->age];
33     }
34 
35     //确定有多少个数据在当前元素的前面
36     for (int i = 1; i < nMaxAge; ++i)
37     {
38         nCount[i] += nCount[i-1];
39     }
40 
41     vector<StudentInfo> StudentSorted;
42     StudentSorted.reserve(vec.size()); //使用reserve预分配空间,这些空间是否有初始值呢?
43     StudentSorted.resize(vec.size());
44     for (int i = 0; i < vec.size(); ++ i)
45     {
46         int index = --nCount[vec[i].age];
47          StudentSorted[index] = vec[i];
48     }
49 
50     //将StudentSorted数据复制到vec中。
51     vec.swap(StudentSorted);
52     //for_each(vec.begin(), vec.end(), student);
53     free(nCount);
54     nCount = NULL;
55 }
56 int main()
57 {
58     vector<StudentInfo> vec;
59     //初始化vec中的数据
60     for (int i = 0; i < 20++i)
61     {
62         StudentInfo stuInfo = {i%10"qinlei""CS"};
63         vec.push_back(stuInfo);
64     }
65 
66     //开始排序
67     Countsort(vec, 20);
68     //打印排序后的结果
69     for_each(vec.begin(), vec.end(), student);
70     return 0;
71 }

posted on 2011-06-04 23:50 MrRightLeft 阅读(218) 评论(0)  编辑 收藏 引用 所属分类: C/C++


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年6月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

导航

统计

随笔分类

随笔档案

文章分类

文章档案

搜索

最新评论

阅读排行榜

评论排行榜