1 /*
 2  *Author: ZhangHaiba
 3  *Date:2014-1-10
 4  *File: shell_sort.c
 5  *
 6  *a shell sort demo
 7  */
 8 
 9 #include <stdio.h>
10 #define N 512;
11 
12 //public
13 void shell_sort(int*, int);
14 void shell_sort2(int*, int);
15 void set_array(int*, int);
16 void show_array(int*, int);
17 //private
18 void swap(int*, int*);
19 
20 int array[512];
21 
22 int main(void)
23 {
24     int n;
25 
26     scanf("%d", &n);
27     set_array(array, n);
28     shell_sort(array, n);
29     show_array(array, n);
30     return 0;
31 }
32 
33 void shell_sort(int *a, int n)
34  {
35      int gap, i, j, key;
36      
37      for (gap = n/2; gap > 0; gap /= 2)
38          for (i = 0; i < n; ++i) {
39              key = a[i];
40              for (j = i-gap; j >= 0 && a[j] > key; j -= gap)
41                  a[j+gap] = a[j];
42              a[j+gap] = key;
43          }
44  }
45 
46 void shell_sort2(int *a, int n)
47  {
48      int gap, i, j;
49      
50      for (gap = n/2; gap > 0; gap /= 2)
51          for (i = 0; i < n; ++i)
52              for (j = i-gap; j >= 0 && a[j] > a[j+gap]; j -= gap)
53                  swap(&a[j], &a[j+gap]);
54  }
55 
56 void set_array(int *a, int n)
57 {
58     int i;
59     
60     for (i = 0; i < n; ++i)
61         scanf("%d", a+i);
62 }
63 
64 void show_array(int *a, int n)
65 {
66     int i;
67 
68     for (i = 0; i < n; ++i)
69         printf(i == n-1 ? "%d\n" : "%d ", a[i]);
70 }
71 
72 void swap(int *a, int *b)
73 {
74     int tmp = *a;
75     *a = *b;
76     *b = tmp;
77 }