排序（3）希尔(Donald L. Shell)排序

yzc164

　　最近学到希尔排序，感觉理解非常费劲。下面是自己总结的希尔排序，希望自己以后不要忘了。嘿嘿。希尔排序其实是高级插入排序，所以学习希尔排序之前需要了解插入排序。
　　一、希尔排序过程：
　　1，首先根据公式h = h*3 + 1，递归求出h的值；即让h=1，一直递归到h < length结束，得到h。
　　例如：长度是10的数组，h = 4。
　　2，公式递减地进行插入排序
　　for(按公式递减间隔){
　　//开始插入排序过程
　　for(从第二个间隔位置；到末尾；+1){
   for(从第二个间隔位置；>=0； -=间隔)
　　}
　　}
　　例如：3,7,8,0,9,5,4,1,6,2
　　方括号：代表（第二个间隔位置）
　　圆括号：代表与方括号一起进行插入排序的元素
　　h=4
　　1，[(3), 7, 8, 0, [9], 5, 4, 1, 6, 2] => [(3), 7, 8, 0, [9], 5, 4, 1, 6, 2]
2，[3, (7), 8, 0, 9, [5], 4, 1, 6, 2] => [3, [5], 8, 0, 9, (7), 4, 1, 6, 2]
3，[3, 5, (8), 0, 9, 7, [4], 1, 6, 2] => [3, 5, [4], 0, 9, 7, (8), 1, 6, 2]
4，[3, 5, 4, (0), 9, 7, 8, [1], 6, 2] => [3, 5, 4, (0), 9, 7, 8, [1], 6, 2]
5，[(3), 5, 4, 0, (9), 7, 8, 1, [6], 2] => [(3), 5, 4, 0, [6], 7, 8, 1, (9), 2]
6，[3, (5), 4, 0, 6, (7), 8, 1, 9, [2]] => [3, [2], 4, 0, 6, (5), 8, 1, 9, (7)]
　　h=1
7，[(3), [2], 4, 0, 6, 5, 8, 1, 9, 7] => [[2], (3), 4, 0, 6, 5, 8, 1, 9, 7]
8，[(2), (3), [4], 0, 6, 5, 8, 1, 9, 7] => [(2), (3), [4], 0, 6, 5, 8, 1, 9, 7]
9，[(2), (3), (4), [0], 6, 5, 8, 1, 9, 7] => [[0], (2), (3), (4), 6, 5, 8, 1, 9, 7]
10，[(0), (2), (3), (4), [6], 5, 8, 1, 9, 7] => [(0), (2), (3), (4), [6], 5, 8, 1, 9, 7]
11，[(0), (2), (3), (4), (6), [5], 8, 1, 9, 7] => [(0), (2), (3), (4), [5], (6), 8, 1, 9, 7]
12，[(0), (2), (3), (4), (5), (6), [8], 1, 9, 7] => [(0), (2), (3), (4), (5), (6), [8], 1, 9, 7]
13，[(0), (2), (3), (4), (5), (6), (8), [1], 9, 7] => [(0), [1], (2), (3), (4), (5), (6), (8), 9, 7]
14，[(0), (1), (2), (3), (4), (5), (6), (8), [9], 7] => [(0), (1), (2), (3), (4), (5), (6), (8), [9], 7]
15，[(0), (1), (2), (3), (4), (5), (6), (8), (9), [7]] => [(0), (1), (2), (3), (4), (5), (6), [7], (8), (9)]
　　其中
　　步骤1，5为对索引0，4，8的一个完整的插入排序
　　步骤2，6为对索引1，5     的一个完整的插入排序
　　步骤3......
　　步骤4.....
　　以此类推。
　　二、看下面的程序
　　while(h > 0) 是过程1公式递减
　　for(int i = h; i < data.length; i++) 和while(k >= 0) 完成了过程2，过程2实际穿插地合并了若干个插入排序。
　　上程序：

public static int[] data = {3,7,8,0,9,5,4,1,6,2};
public static void main(String[] args) {
System.out.println(Arrays.toString(data));
int h = 1;
//求间隔公式
while(h <= data.length / 3){
h = h*3 + 1;
}
while(h > 0){ //减小间隔
//插入排序
for(int i = h; i < data.length; i++){//合并了两个循环过程
int temp = data;
int j = i;
while(j > h-1 && data[j - h] >= temp){
data[j] = data[j - h];
j -= h;
}
data[j] = temp;
}
h = (h - 1) / 3;
}
System.out.println(Arrays.toString(data));