1 #include "stdio.h"
 2 #include "stdlib.h"
 3 typedef int ElemType;
 4 //直接插入排序
 5 void InsertSort(ElemType A[], int n) {
 6     int i, j;
 7     for (i =2; i <= n; i++) {
 8         A[0] = A[i];
 9         j = i - 1;
10         while (A[0] < A[j]) {
11             A[j+1] = A[j];
12             j = j - 1;
13         }
14         A[j + 1] = A[0];
15     }
16 }
17 //折半插入排序
18 void BinSort(ElemType A[], int n) {
19     int i, j, low, high, mid;
20     for (i = 2; i <= n; i++) {
21         A[0] = A[i];
22         low = 1;
23         high = i - 1;
24         while (low <= high) {
25             mid = (low + high) / 2;
26             if (A[mid] > A[0])
27                 high = mid - 1;
28             else
29                 low = mid + 1;
30         }
31         for (j = i - 1; j >= high + 1; --j)
32             A[j + 1] = A[j];
33         A[high + 1] = A[0];//A[low]=A[0];
34     }
35 }
36 //希尔排序
37 void ShellInsert(ElemType A[], int n,int delta) {
38     int i, j;
39     for(i=1+delta;i<=n;i++)
40         if (A[i] < A[i - delta]) {
41             A[0] = A[i];
42             for (j = i - delta; j > 0 && A[0] < A[j]; j -= delta)
43                 A[j + delta] = A[j];
44             A[j + delta] = A[0];
45         }
46 }
47 void ShellSort(ElemType A[], int n, int delta[], int dn) {
48     int i, j;
49     for (i = 0; i <= n - 1; ++i)
50         ShellInsert(A, n, delta[i]);
51 }
52 //希尔建议希尔排序
53 void ShellSort(ElemType A[], int n) {
54     int dk,i,j;
55     for(dk=n/2;dk>=1;dk=dk/2)
56         for (i = dk + 1; i <= n; ++i) {
57             if (A[i] < A[i - dk]) {
58                 A[0] = A[i];
59                 for (j = i - dk; j > 0 && A[0] < A[j]; j -= dk)
60                     A[j + dk] = A[j];
61                 A[j + dk] = A[0];
62             }
63         }
64 }