未加星标

Java排序算法--希尔排序(Shellsort)

字体大小 | |
[系统(linux) 所属分类 系统(linux) | 发布者 店小二04 | 时间 20160901 | 作者 红领巾 ] 0人收藏点击收藏
希尔排序

希尔排序:它通过比较相距一定间隔的元素来工作,各趟比较所用的距离随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止。希尔排序也叫缩减增量排序(diminishing increment sort)。

希尔排序使用一个序列h1,h2,h3,…,ht,叫做增量序列(increment sequence)。在使用增量hk的一趟排序之后,对于每一个i我们都有a[i]≤a[i+hk],所有相隔hk的元素都被排序,此时称文件是hk排序的(hk-sorted)。希尔排序的一个重要性质:一个hk排序的文件(然后将是hk-1排序的)保持它的hk排序性。

hk排序的一般做法是,对于hk,hk+1,...,N-1中的每一个位置i,把其上的元素放到i,i-hk,i-2hk,...中的正确位置上。一趟hk排序的作用就是对hk个独立的子数组执行一次插入排序。

Java排序算法--希尔排序(Shellsort)

Shell建议序列:ht=N/2值的下界,hk=hk+1/2值的下界。使用希尔增量的希尔排序:

/**
* Shellsort,using Shell's(poor) increments
* @param a an array of Comparable items
*/
public static <AnyType extends Comparable<? super AnyType>> void shellsort(AnyType[] a){
int j;
for(int gap=a.length/2;gap>0;gap/=2){
for(int i=gap;i<a.length;i++){
AnyType tmp = a[i];
for(j=i;j>=gap&&tmp.compareTo(a[j-gap])<0;j-=gap){
a[j] = a[j-gap];
}
a[j] = tmp;
}
}
}
希尔排序的最坏情形分析

使用希尔增量时希尔排序的最坏情形运行时间为O(N2)。

Hibbard提出一个稍微不同的增量序列,它的增量形如1,3,7,...,2K-1。虽然这些增量几乎是相同的,但关键的区别是相邻的增量没有公因子。

使用Hibbard增量的希尔排序的最坏情形运行时间为O(N3/2)。

Sedgewick提出几种增量序列,其最坏情形运行时间(也是可以达到的)为O(N4/3)。其中最好的序列{1,5,19,41,109,...},该序列中的项或者是9*4i-9*2i+1形式,或者是4i-3*2i+1形式。

本文地址:http://www.linuxidc.com/Linux/2016-09/135314.htm


Java排序算法--希尔排序(Shellsort)

本文系统(linux)相关术语:linux系统 鸟哥的linux私房菜 linux命令大全 linux操作系统

主题: 算法JavaLinux
分页:12
转载请注明
本文标题:Java排序算法--希尔排序(Shellsort)
本站链接:http://www.codesec.net/view/483472.html
分享请点击:


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 系统(linux) | 评论(0) | 阅读(23)