排序（3）希尔(Donald L. Shell)排序
最近学到希尔排序，感觉理解非常费劲。下面是自己总结的希尔排序，希望自己以后不要忘了。嘿嘿。希尔排序其实是高级插入排序，所以学习希尔排序之前需要了解插入排序。一、希尔排序过程：
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, , 5, 4, 1, 6, 2] => [(3), 7, 8, 0, , 5, 4, 1, 6, 2]
2，, 4, 1, 6, 2] => , 8, 0, 9, (7), 4, 1, 6, 2]
3，, 1, 6, 2] => , 0, 9, 7, (8), 1, 6, 2]
4，, 6, 2] => , 6, 2]
5，[(3), 5, 4, 0, (9), 7, 8, 1, , 2] => [(3), 5, 4, 0, , 7, 8, 1, (9), 2]
6，] => , 4, 0, 6, (5), 8, 1, 9, (7)]
h=1
7，[(3), , 4, 0, 6, 5, 8, 1, 9, 7] => [, (3), 4, 0, 6, 5, 8, 1, 9, 7]
8，[(2), (3), , 0, 6, 5, 8, 1, 9, 7] => [(2), (3), , 0, 6, 5, 8, 1, 9, 7]
9，[(2), (3), (4), , 6, 5, 8, 1, 9, 7] => [, (2), (3), (4), 6, 5, 8, 1, 9, 7]
10，[(0), (2), (3), (4), , 5, 8, 1, 9, 7] => [(0), (2), (3), (4), , 5, 8, 1, 9, 7]
11，[(0), (2), (3), (4), (6), , 8, 1, 9, 7] => [(0), (2), (3), (4), , (6), 8, 1, 9, 7]
12，[(0), (2), (3), (4), (5), (6), , 1, 9, 7] => [(0), (2), (3), (4), (5), (6), , 1, 9, 7]
13，[(0), (2), (3), (4), (5), (6), (8), , 9, 7] => [(0), , (2), (3), (4), (5), (6), (8), 9, 7]
14，[(0), (1), (2), (3), (4), (5), (6), (8), , 7] => [(0), (1), (2), (3), (4), (5), (6), (8), , 7]
15，[(0), (1), (2), (3), (4), (5), (6), (8), (9), ] => [(0), (1), (2), (3), (4), (5), (6), , (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 >= temp){
data = data;
j -= h;
}
data = temp;
}
h = (h - 1) / 3;
}
System.out.println(Arrays.toString(data));
页:
[1]