顺序表-希尔排序

 1 #include<bits/stdc++.h>
 2 #define MAX 100
 3 typedef struct{
 4     int *Elem;
 5     int length;
 6 }SeqList; 
 7 void creat(SeqList &s)
 8 {
 9     s.Elem = (int*)malloc(MAX*sizeof(int));
10     if(!s.Elem){
11         printf("创建失败\n");
12         exit(1);
13     }
14     int n,m,j;
15     printf("请输入元素以-1结束：\n");
16     scanf("%d",&n);
17     s.length = 0;
18     while(n!=-1){
19         s.Elem[s.length++] = n;
20         scanf("%d",&n);
21     }
22 }
23 void print(SeqList s)
24 {
25     int i;
26     for(i=0;i<s.length;i++){
27         printf("%d ",s.Elem[i]);
28     }
29 }
30 void ShellSort(SeqList &s)
31 {
32     int gap,i,j,temp,len = s.length,k;
33     for(gap=len/2;gap>0;gap/=2){
34         for(i=0;i<gap;++i){
35             for(j=i+gap;j<len;j+=gap){
36                 temp = s.Elem[j];
37                 k = j-gap;
38                 while(k>=0&&s.Elem[k]>temp){
39                     s.Elem[k+gap] = s.Elem[k];
40                     k -=gap;
41                 }
42                 s.Elem[k+gap] = temp;
43             }
44         }
45     }
46 }
47 void ShellSort1(SeqList &s){
48     int d,i,j,temp;
49     for(d=s.length/2;d>0;d/=2)
50     {
51         for(i=d+1;i<s.length;i++){
52             temp =     s.Elem[i];
53             for(j = i-d;j>0&&temp<s.Elem[j];j = j-d){
54                 s.Elem[j+d] = s.Elem[j];
55             }
56             s.Elem[j+d] = temp;
57         }
58     }
59     for(i=1;i<s.length;i++){
60         if(s.Elem[0]<s.Elem[i]){
61             temp = s.Elem[0];
62             for(j=1;j<i;j++){
63                 s.Elem[j-1] = s.Elem[j];
64             }
65             s.Elem[j-1] = temp;
66             return;
67         }
68     }
69 }
70 int main(){
71     SeqList s;
72     creat(s);
73     ShellSort(s);
74     print(s);
75 }