最近学到希尔排序,感觉理解非常费劲。下面是自己总结的希尔排序,希望自己以后不要忘了。嘿嘿。希尔排序其实是高级插入排序,所以学习希尔排序之前需要了解插入排序。
一、希尔排序过程:
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[i]; 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));
相关推荐
Knuth 著).pdf size=17775679 crc32=7B18B9F4 ===== 本PDF共3个文件 计算机程序设计艺术(第二版,中文版,第三卷:排序和查找,Donald E. Knuth 著).001 计算机程序设计艺术(第二版,中文版...
Knuth 著).pdf size=17775679 crc32=7B18B9F4 ===== 本PDF共3个文件 计算机程序设计艺术(第二版,中文版,第三卷:排序和查找,Donald E. Knuth 著).001 计算机程序设计艺术(第二版,中文版...
Knuth 著).pdf size=17775679 crc32=7B18B9F4 ===== 本PDF共3个文件 计算机程序设计艺术(第二版,中文版,第三卷:排序和查找,Donald E. Knuth 著).001 计算机程序设计艺术(第二版,中文版...
filename=计算机程序设计艺术(第三版,中文版,第二卷:半数值算法,Donald E.Knuth 著).pdf size=20344330 crc32=4CD7A531 ========= 此PDF共3个文件 计算机程序设计艺术(第三版,中文版,第二卷...
计算机程序设计艺术(中文版,第一卷,Donald E.Knuth 著)(The Art of programming)
filename=计算机程序设计艺术(第三版,中文版,第二卷:半数值算法,Donald E.Knuth 著).pdf size=20344330 crc32=4CD7A531 ========= 此PDF共3个文件 计算机程序设计艺术(第三版,中文版,第二卷...
算法分析论文Donald.E.Knuth算法分析论文Donald.E.Knuth算法分析论文Donald.E.Knuth算法分析论文Donald.E.Knuth算法分析论文Donald.E.Knuth算法分析论文Donald.E.Knuth算法分析论文Donald.E.Knuth算法分析论文Donald...
尼曼的经典教材,半导体物理与器件。非常厚的一本书。
Addison.Wesley.Donald.E.Knuth.The.Art.of.Computer.Programming.Volume.1
[计算机科学经典著作].Addison.Wesley.Donald.E.Knuth.The.Art.of.Computer.Programming.Volume.1.pdf
Computer Graphics C Version 2Ed by Donald Hearn.pdf ) Computer Graphics
Donald E. Knuth, Tracy Larrabee, and Paul M. Roberts This report is based on a course of the same name given at Stanford University during autumn quarter, 1987. Here’s the catalog description:
filename=计算机程序设计艺术(第三版,中文版,第一卷:基本算法,Donald E.Knuth 著).pdf size=15084743 crc32=2C27184E ==== 此PDF共2个文件 只要简单地把.001和.002文件连接起来,即可观看 ...
Addison.Wesley.Donald.E.Knuth.The.Art.of.Computer.Programming.Volume.2
该第一册更新了《计算机编程的艺术》,第1卷,第3版:基础算法,最终将成为该书第4版的一部分。
filename=计算机程序设计艺术(第三版,中文版,第二卷:半数值算法,Donald E.Knuth 著).pdf size=20344330 crc32=4CD7A531 ========= 此PDF共3个文件 计算机程序设计艺术(第三版,中文版,第二卷...
关于计算机科学的重量级论文选集,具有很高的理论性。比较权威。可以供写论文的参考
本资源是以压缩包的形式上传的, 里面是本书的“第3卷(第2版 中文版)排序与查找, 本压缩包里”是一本pdf格式电子书。 本书一共4卷, 其中3本中文版,一本英文版, 会陆续的上传上来。 需要下载的朋友,可以在我的...
This manual describes TEX Version 3.0. Some of the advanced features mentioned here are absent from earlier versions.