排序算法之选择排序

 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 }