希尔排序，升级版的直接插入排序

一、实现思想

　　1、将一个序列，等间隔地取出一个个元素，作为一个子序列　　（这个步骤我称之为「拆」）

　　　　比如 1 2 3 4 5 6 ，间隔为3

　　　　则　　1　　4

　　　　　　 2　　5

　　　　　　　3　　6

　　2、然后将各个子序列进行直接插入排序

　　3、不断缩小间隔，重复以上步骤，直到间隔为1

补充：这个间隔该如何取并没有规定，但是希尔排序的创始人希尔，是取间隔d = length /2;d = d/2;直到d = 1;(length为元素个数)

二、实现图例

三、实现代码

　　这个是在直接插入排序的基础上做了一个增强，和直接插入排序一个，要注意条件的控制

 1 #include <stdio.h>
 2 void ShellSort(int array[], int len)
 3 {
 4     int i, j;
 5     int temp;
 6 
 7     for (int d = len / 2; d >= 1; d = d / 2) //控制要拆多少次
 8     {
 9         for (i = d; i < len; i++) //一个for循环便把各个子序列进行了一遍直接插入排序，巧妙的就在于这个d
10         {
11             temp = array[i];
12             for (j = i - d; j >= 0 && temp < array[j]; j = j - d)
13                 array[j + d] = array[j];
14             array[j + d] = temp;
15         }
16     }
17 }
18 int main(void)
19 {
20     int a[] = {4, 5, 2, 3, 1, 6};
21     for (int i = 0; i < 6; i++)
22         printf("%d    ", a[i]);
23     printf("
");
24     ShellSort(a, 6);
25     for (int i = 0; i < 6; i++)
26         printf("%d    ", a[i]);
27     return 0;
28 }
29 /* 
30 输出
31 ——————————————————————————————————
32 4    5    2    3    1    6    
33 1    2    3    4    5    6  
34 ——————————————————————————————————
35  */

(ps:我这里显示了行号，复制也会一同复制过去。你应该会竖直选择然后删除吧)