elva

shellsort之三


网站: JavaEye  作者: shenyu  链接: http://shenyu.javaeye.com/blog/189563  发表时间: 2008年05月05日

声明:本文系JavaEye网站发布的原创博客文章,未经作者书面许可,严禁任何网站转载本文,否则必将追究法律责任!

插入排序 对基本有序的数组效果非常好,但是对于通常情况则表现一般。假设最小的数字在最右边,升序排序时,这个数则要经过n次交换比较换到最左边。希尔排序则是对插入排序的很好的修正。而且在希尔排序很少出现最坏状况。

希尔排序通过对数组 以一定间隔相隔的位置 进行插入排序,以达到让数据快速出现在它应该出现的位置的周围,使数组逐步接近基本有序。随着间隔的减少,数组越来越接近基本有序,最后间隔为1时,变成标准的插入排序。

数据的间隔有多种算法,一般要求间隔序列之间互质,此处使用Kunth序列:h = h * 3 + 1

希尔排序的时间效率很难从理论上证明,实验表明大约是O(n^(3/2)) ~ O(n^(7/6))之间。

代码如下:

class Shell {
public static void main(String[] args) {
int[] a = {9,8,7,6,5,4,3,2,1};
sort(a);
println(a);
}
private static void println(int[] a) {
for(int i: a) System.out.print(i + " ");
System.out.println();
}
private static void sort(int[] a) {
int h = 1;
while(h <= a.length/3) h = h * 3 + 1;	//产成Kunth序列
while(h > 0) {
for(int i = h; i < a.length; i++) {	//对每个数据进行间隔为h的插入排序
int pos = i;
int temp = a[i];
while(pos >= h && a[pos - h] > temp) {
a[pos] = a[pos-h];
pos -= h;
}
a[pos] = temp;
}
h = (h - 1) / 3;	//减小间隔值
}
}
}
 

posted on 2010-11-01 18:08 叶子 阅读(262) 评论(0)  编辑 收藏 引用 所属分类: 数据结构


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理