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 }