排序算法之计数排序
1 /*
2 用UVA 11462 Age Sort来验证算法的正确性
3 */
4 #include <cstdio>
5 #include <cstring>
6 #include <algorithm>
7 #include <string>
8 #include <cmath>
9 #include <vector>
10 #include <map>
11 #include <set>
12 #include <cmath>
13 using namespace std;
14
15 const int MAX_N = 2000000 + 10;
16 int a[MAX_N], w[MAX_N], p[MAX_N], o[MAX_N];
17
18 void BucketSort(int *a, int n, int mx)
19 {
20 memset (w, 0, sizeof (w));
21 for (int i=1; i<=n; ++i)
22 {
23 w[a[i]]++;
24 }
25 for (int i=1; i<=mx; ++i)
26 {
27 w[i] += w[i-1];
28 }
29 for (int i=1; i<=n; ++i)
30 {
31 p[i] = w[a[i]];
32 w[a[i]]--;
33 }
34 for (int i=1; i<=n; ++i)
35 {
36 o[p[i]] = i;
37 }
38 }
39
40 int main(void) //UVA 11462 Age Sort
41 {
42 //freopen ("rand_small.in", "r", stdin);
43 int n;
44
45 while (scanf ("%d", &n) != EOF && n)
46 {
47 int mx = 0;
48 for (int i=1; i<=n; ++i)
49 {
50 scanf ("%d", &a[i]);
51 if (a[i] > mx)
52 {
53 mx = a[i];
54 }
55 }
56 BucketSort (a, n, mx);
57
58 for (int i=1; i<=n; ++i)
59 {
60 printf ("%d%c", a[o[i]], (i==n) ? ‘\n‘ : ‘ ‘);
61 }
62 }
63
64 return 0;
65 }
1 /*
2 用UVA 11462 Age Sort来验证算法的正确性
3 我不知道它究竟是啥算法,计数,基数or桶排序?不过比上一个好的感觉:)
4 */
5 #include <cstdio>
6 #include <algorithm>
7 #include <cstring>
8 using namespace std;
9
10 const int MAX_N = 2000000 + 10;
11 int a[MAX_N];
12 int num[MAX_N];
13
14 void BucketSort(int *a, int p, int r)
15 {
16 for (int i=p; i<=r; ++i)
17 {
18 num[a[i]]++;
19 }
20 }
21
22 int main(void) //UVA 11462 Age Sort
23 {
24 freopen ("rand_small.in", "r", stdin);
25
26 int n;
27 while (scanf ("%d", &n) != EOF && n)
28 {
29 memset (num, 0, sizeof (num));
30 int mx = -1;
31 for (int i=1; i<=n; ++i)
32 {
33 scanf ("%d", &a[i]);
34 if (a[i] > mx) mx = a[i];
35 }
36
37 BucketSort (a, 1, n);
38
39 for (int i=0; i<=mx; ++i)
40 {
41 if (num[i] == 0) continue;
42 else
43 {
44 for (int j=1; j<=num[i]; ++j)
45 {
46 printf ("%d%c", i, (i==mx && j==num[i]) ? ‘\n‘ : ‘ ‘);
47 }
48 }
49 }
50 }
51
52 return 0;
53 }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。