【6】算法排序 （希尔排序）看一遍就懂！

 希尔排序的具体实现思路是：先将整个记录表分割成若干部分，分别进行直接插入排序，然后再对整个记录表进行一次直接插入排序。、

 总结 : 不断缩小增量(gap)的排序过程

 时间复杂度:

 希尔排序相对来说，思路非常简单，但是很多网络文章，描述的及其麻烦，扰乱读者理解，这里我用最清晰方式解析；

 注: int gap = n/2; 这里的间距，所代表的意思   并不是gap左边的所有数为一组进行插入排序， gap右边的所有数为一组进行插入排序

　   假设数组为 [10, 20, 30 ,40, 1, 2, 3, 4]   

　   第一轮分组 ：gap = 8/2 = 4

　   数组的下标从0开始， 分组间距为4

　　分组情况为 

　　第一组: 10   1

　　第二组: 20   2

　　第三组: 30   3 

　　第四组: 40   4

　　每组进行插入排序，则为 [1, 2, 3, 4 , 10, 20, 30, 40] 

　　第二轮分组：gap = 4/2 = 2

　　数组的下标从0开始， 分组间距为4

　　第一组: 1   3  10  30

　　第二组: 2   4  20  40

　　以此类推......

如果还不明白，再重新看一个例子:

int a[11] = {33, 40, 1, 14, 7, 35, 27, 9, 55, 80, 61};

第一轮分组 ：gap = 11/2 = 5    这里分组间距随意分都行，为了方便理解，通常喜欢取中位数

　　分组情况为 

　　第一组: 33   35  61   ->  33  35  61

　　第二组: 40   27         ->  27  40

　　第三组: 1     9  　　  ->  1     9

　　第四组: 14   55 　　 -> 14   55

       第五组:  7    80　　  ->  7    80

       每组进行插入排序，则为 [33   27  1  14  7  35  40  9  55  80  61] 

第二轮分组 ：gap = 5/2 = 2   

　　分组情况为 [33   27  1  14  7  35  40  9  55  80  61] 

　　第一组: 33    1      7     40    55    61      ->  1   7   33   40   55  61

　　第二组: 27    14    35   9      80              ->  9  14   27  35   80 

       每组进行插入排序，则为 [1,  9,  7, 14, 33,  27,  40,  35, 55, 80, 61] 

第三轮分组 ：gap = 2/2 = 1  最后一轮

      分组情况为 [33   27  1  14  7  35  40  9  55  80  61] 

　   直接进行正常的插入排序

 测试代码

void ShellSort(int * a, int n)
{
        // 设置间距
        int gap = n/2;
        while(gap > 0) {
                int i, j, key;
                for(i=gap; i<n; i++) {
                        key=a[i];
                        for(j=i; j>=gap && key<a[j-gap]; j-=gap) {
                                a[j] = a[j-gap];
                        }
                        a[j] = key;
                }
                printf("当前间距是gap:%d
", gap);
                PrintSort(a, n);
                gap = gap/2;
        }
        printf("希尔排序:
");
        PrintSort(a, n);
}

int main()
{
        int a[11] = {33, 40, 1, 14, 7, 35, 27, 9, 55, 80, 61};
        ShellSort(a, 11);
}

 

完整代码

#include <stdio.h>

void PrintSort(int * a, int n)
{
        int i;
        for (i=0; i<n; i++) {
                printf("%d  ", a[i]);
        }
        printf("

");
}

void ShellSort(int * a, int n)
{
        // 设置间距
        int gap = n/2;
        while(gap > 0) {
                int i, j, key;
                // 每一趟采用插入排序
       
                for(i=gap; i<n; i++) {
                        key=a[i];
                        // 与直接插入一致  for(j=i; j-gap>=0 && key<a[j-gap]; j=j-gap)
                        for(j=i; j>=gap && key<a[j-gap]; j-=gap) {
                                a[j] = a[j-gap];
                        }
                        a[j] = key;
                }
                // 新的一轮，开始
                gap = gap/2;
        }
        printf("希尔排序:
");
        PrintSort(a, 10);
}

void InsertSort(int * a, int n)
{
        int i, j, tmp;
        for(i=1; i<n; i++) {
                tmp = a[i];
                for(j=i; j>=1 && tmp<a[j-1]; j--) {
                        a[j] = a[j-1];
                }
                a[j] = tmp;
        }
        printf("直接插入排序:
");
        PrintSort(a, 10);
}

int main()
{
        int b[10] = {10, 3, 20, 4, 30, 5, 40, 6, 2, 1};
        InsertSort(b, 10);

        int a[10] = {10, 3, 20, 4, 30, 5, 40, 6, 2, 1};
        ShellSort(a, 10);
}