希尔排序法（缩小增量法）

2016-10-25 16:51:49

首先，要明白希尔排序法是什么。它是一种改进版的直接插入法，它是将整个无序列分割成若干小的子序列分别进行插入排序的方法。

 1 #include<stdio.h>
 2 
 3 //希尔排序法
 4 void shell_sort(int a[],int n);
 5 int main()
 6 {
 7     int i;
 8     int a[6];
 9     printf("please enter five numbers:
");
10     for(i=1;i<6;i++)
11     {
12         scanf("%d",&a[i]);
13     }
14     shell_sort(a,5);
15     printf("after number:
");
16     for(i=1;i<6;i++)
17     {
18         printf("%4d",a[i]);
19     }
20     printf("
");
21 }
22 
23 void shell_sort(int a[],int n)
24 {
25     int i,j;
26     int d;
27     d=n/2;
28     while(d)
29     {
30         for(i=d+1;i<=n;i++)
31         {
32             a[0]=a[i];
33             j=i-d;
34             while(a[0]>=a[j]  && j>0)
35             {
36                 a[j+d]=a[j];
37                 j=j-d;
38             }
39             a[j+d]=a[0];
40         }
41         d=d/2;
42     }
43 }

这就和直接插入法非常类似了。因此其也有另一种形式。

 1 #include<stdio.h>
 2 
 3 //希尔排序法
 4 void shell_sort(int a[],int n);
 5 int main()
 6 {
 7     int i;
 8     int a[6];
 9     printf("please enter five numbers:
");
10     for(i=1;i<6;i++)
11     {
12         scanf("%d",&a[i]);
13     }
14     shell_sort(a,5);
15     printf("after number:
");
16     for(i=1;i<6;i++)
17     {
18         printf("%4d",a[i]);
19     }
20     printf("
");
21 }
22 
23 void shell_sort(int a[],int n)
24 {
25     int i;
26     int d;
27     d=n/2;
28     while(d)
29     {
30         for(i=d+1;i<=n;i++)
31         {
32             a[0]=a[i];
33             
34             while(a[0]>=a[i-d]  && i>d)
35             {
36                 a[i]=a[i-d];
37                 i=i-d;
38             }
39             a[i]=a[0];
40         }
41         d=d/2;
42     }
43 }

发现两次while循环后，a[0]复制给谁的异同了吗？

两个不一样，但是是为什么呢？

其实，最后a[0]赋予的值和最后一个相同，即与a[i]=a[i-d]中的a[i-d]相同。