计数排序实现：以学生年龄对学生信息进行排序。
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, 0, sizeof(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 }