排序算法之插入排序

浏览数：19 / 时间：2015年06月08日

题目传送门

 1 /*
 2     插入排序——扑克牌排序
 3     用zstu3539题目来验证算法的正确性
 4 */
 5 #include <cstdio>
 6 #include <iostream>
 7 #include <algorithm>
 8 #include <ctime>
 9 #include <cstdlib>
10 using namespace std;
11 
12 const int maxn = 1000000 + 10;
13 const int INF = 0x3f3f3f3f;
14 int a[maxn];
15 
16 void InsertSort(int *a, int n)
17 {
18     for (int i=2; i<=n; ++i)
19     {
20         if (a[i-1] > a[i])
21         {
22             int x = a[i];
23             int j = i - 1;
24             while (j > 0 && a[j] > x)
25             {
26                 a[j+1] = a[j];
27                 --j;
28             }
29             a[j+1] = x;
30         }
31     }
32 }
33 
34 
35 int main(void)
36 {
37     //freopen ("rand_small.in", "r", stdin);
38     int n;
39 
40     while (scanf ("%d", &n) != EOF)
41     {
42         if (n == 0)
43             continue;
44         for (int i=1; i<=n; ++i)
45         {
46             scanf ("%d", &a[i]);
47         }
48     
49         InsertSort (a, n);
50 
51         bool flag = true;
52         for (int i=1; i<=n; ++i)
53         {
54             if (flag)
55             {
56                 printf ("%d", a[i]);
57                 flag = false;
58             }
59             else
60                 printf (" %d", a[i]);
61         }
62         puts ("");
63     }
64 
65     return 0;
66 }