希尔排序

​

基本思想

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2 =1(

img

img

…

该方法实质上是一种分组插入方法

比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。

一般的初次取序列的一半为增量，以后每次减半，直到增量为1。

给定实例的shell排序的排序过程

假设待排序文件有10个记录，其关键字分别是：

49，38，65，97，76，13，27，49，55，04。

增量序列的取值依次为：

5，2，1

图片演示

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// 基于插入排序
#include <stdio.h>
#include <stdlib.h>

void insert_sort (int a[],int gap,int len){
    for (int i=gap;i<len;i++){
        int temp = a[i];
        int j = i-gap;
        /*
        while (a[j+gap]>a[j] && j>=0){
            a[j+gap] = a[j];
            j-=gap;
        }  
        // 倒序 
        */
        
        while (a[j]>temp && j>=0){
            a[j+gap] = a[j];
            j-=gap;
        }
        
        a[j+gap] = temp;
    }
}

void shell_sort (int a[],int len){
    
    int d = len/2;
    while (d>=1){
        insert_sort(a,d,len);
        d/=2;
    }
}

int main (){
    int a[]={1,6,5,4,8,9,55,16,43};
    int len =sizeof(a)/sizeof(a[0]);
    shell_sort(a,len);
    for (int i=0;i<len;i++){
        printf("%d\t",a[i]);
    }
    system("pause");
    return 0;
}

输出结果

1 4 5 6 8 9 16 43 55