1 /*
2 用zstu3539题目来验证算法的正确性
3 */
4 #include <cstdio>
5 #include <iostream>
6 #include <algorithm>
7 #include <ctime>
8 #include <cstdlib>
9 using namespace std;
10
11 const int maxn = 1000000 + 10;
12 const int INF = 0x3f3f3f3f;
13 int a[maxn];
14
15 void SelectSort(int *a, int n)
16 {
17 for (int i=1; i<=n; ++i)
18 {
19 int mn = a[i]; int k = i;
20 for (int j=i+1; j<=n; ++j)
21 {
22 if (mn > a[j])
23 {
24 mn = a[j];
25 k = j;
26 }
27 }
28 if (mn != a[i])
29 swap (a[i], a[k]);
30 }
31 }
32
33 void SelectSort_2(int *a, int n) //每次分配最大值和最小值，还有bug
34 {
35 for (int i=1; i<=n/2+1; ++i)
36 {
37 int mn_id = i, mx_id = n - i + 1;
38 for (int j=i+1; j<=n-i; ++j)
39 {
40 if (a[j] > a[mx_id])
41 {
42 mx_id = j; continue;
43 }
44 if (a[j] < a[mn_id]) mn_id = j;
45 }
46 swap (a[i], a[mn_id]);
47 swap (a[n-i+1], a[mx_id]);
48 }
49 }
50
51 int main(void)
52 {
53 //freopen ("rand_small.in", "r", stdin);
54 int n;
55
56 while (scanf ("%d", &n) != EOF)
57 {
58 if (n == 0)
59 continue;
60 for (int i=1; i<=n; ++i)
61 {
62 scanf ("%d", &a[i]);
63 }
64
65 SelectSort (a, n);
66 //SelectSort_2 (a, n);
67
68 bool flag = true;
69 for (int i=1; i<=n; ++i)
70 {
71 if (flag)
72 {
73 printf ("%d", a[i]);
74 flag = false;
75 }
76 else
77 printf (" %d", a[i]);
78 }
79 puts ("");
80 }
81
82 return 0;
83 }
