希尔排序
希尔思想介绍
希尔算法的本质是缩小增量排序,是对直接插入排序算法的改进。一般直接插入排序的时间复杂度为O ( n^2 ) ,但是当数列基本有序时,如果按照有数列顺序排时,时间复杂度将改善到O( n ),另外,因直接插入排序算法简单,如果待排序列规模不很大时效率也较高,Shell 根据这两点分析结果进行了改进,将待排记录序列以一定的增量间隔h 分割成多个子序列,对每个子序列分别进行一趟直接插入排序, 然后逐步减小分组的步长h ,对于每一个步长h 下的各个子序列进行同样方法的排序,直到步长为1 时再进行一次整体排序。
因为不管记录序列多么庞大,关键字多么混乱,在先前较大的分组步长h 下每个子序列的规模都不大,用直接插入排序效率都较高。 尽管在随后的步长h 递减分组中子序列越来越大,但由于整个序列的有序性也越来越明显,则排序效率依然较高。这种改进抓住了直接插入排序的两点本质,大大提高了它的时间效率。
希尔增量研究
综上所述:
(1) 希尔排序的核心是以某个增量h 为步长跳跃分组进行插入排序,由于分组的步长h 逐步缩小,所以也叫“缩小增量排序”插入排序。其关键是如何选取分组的步长序列ht ,. . . , hk ,. . . , h1 , h0 才能使得希尔方法的时间效率最高;
(2) 待排序列记录的个数n 、跳跃分组步长逐步减小直到为1时所进行的扫描次数T、增量的和、记录关键字比较的次数以及记录移动的次数或各子序列中的反序数等因素都影响希尔算法的时间复杂度:其中记录关键字比较的次数是重要因素,它主要取决于分组步长序列的选择;
(3) 希尔方法是一种不稳定排序算法,因为其排序过程中各趟的步长不同,在第k 遍用hk作为步长排序之后,第k +1 遍排序时可能会遇到多个逆序存在,影响排序的稳定性。
试验结果表明,SHELL 算法的时间复杂度受增量序列的影响明显大于其他因素,选取恰当的增量序列能明显提高排序的时间效率,我们认为第k 趟排序扫描的增量步长为 2^k - 1 ,即增量序列为. . . 2^k - 1 ,. . . ,15 ,7 ,3 ,1时较为理想,但它并不是唯一的最佳增量序列,这与其关联函数目前尚无确定解的理论结果是一致的。
Java代码
package sort;
import java.util.Comparator;
/**
* 希尔排序算法
* @author jzj
* @date 2009-12-5
*
* @param <E>
*/
public class ShelltSort<E extends Comparable<E>> extends Sort<E> {
/**
* 排序算法的实现,对数组中指定的元素进行排序
* @param array 待排序的数组
* @param from 从哪里开始排序
* @param end 排到哪里
* @param c 比较器
*/
public void sort(E[] array, int from, int end, Comparator<E> c) {
//初始步长,实质为每轮的分组数
int step = initialStep(end - from + 1);
//第一层循环是对排序轮次进行循环。(step + 1) / 2 - 1 为下一轮步长值
for (; step >= 1; step = (step + 1) / 2 - 1) {
//对每轮里的每个分组进行循环
for (int groupIndex = 0; groupIndex < step; groupIndex++) {
//对每组进行直接插入排序
insertSort(array, groupIndex, step, end, c);
}
}
}
/**
* 直接插入排序实现
* @param array 待排序数组
* @param groupIndex 对每轮的哪一组进行排序
* @param step 步长
* @param end 整个数组要排哪个元素止
* @param c 比较器
*/
private void insertSort(E[] array, int groupIndex, int step, int end, Comparator<E> c) {
int startIndex = groupIndex;//从哪里开始排序
int endIndex = startIndex;//排到哪里
/*
* 排到哪里需要计算得到,从开始排序元素开始,以step步长,可求得下元素是否在数组范围内,
* 如果在数组范围内,则继续循环,直到索引超现数组范围
*/
while ((endIndex + step) <= end) {
endIndex += step;
}
// i为每小组里的第二个元素开始
for (int i = groupIndex + step; i <= end; i += step) {
for (int j = groupIndex; j < i; j += step) {
E insertedElem = array[i];
//从有序数组中最一个元素开始查找第一个大于待插入的元素
if (c.compare(array[j], insertedElem) >= 0) {
//找到插入点后,从插入点开始向后所有元素后移一位
move(array, j, i - step, step);
array[j] = insertedElem;
break;
}
}
}
}
/**
* 根据数组长度求初始步长
*
* 我们选择步长的公式为:2^k-1,2^(k-1)-1,...,15,7,3,1 ,其中2^k 减一即为该步长序列,k
* 为排序轮次
*
* 初始步长:step = 2^k-1
* 初始步长约束条件:step < len - 1 初始步长的值要小于数组长度还要减一的值(因
* 为第一轮分组时尽量不要分为一组,除非数组本身的长度就小于等于4)
*
* 由上面两个关系试可以得知:2^k - 1 < len - 1 关系式,其中k为轮次,如果把 2^k 表 达式
* 转换成 step 表达式,则 2^k-1 可使用 (step + 1)*2-1 替换(因为 step+1 相当于第k-1
* 轮的步长,所以在 step+1 基础上乘以 2 就相当于 2^k 了),即步长与数组长度的关系不等式为
* (step + 1)*2 - 1 < len -1
*
* @param len 数组长度
* @return
*/
private static int initialStep(int len) {
/*
* 初始值设置为步长公式中的最小步长,从最小步长推导出最长初始步长值,即按照以下公式来推:
* 1,3,7,15,...,2^(k-1)-1,2^k-1
* 如果数组长度小于等于4时,步长为1,即长度小于等于4的数组不且分组,此时直接退化为直接插
* 入排序
*/
int step = 1;
//试探下一个步长是否满足条件,如果满足条件,则步长置为下一步长
while ((step + 1) * 2 - 1 < len - 1) {
step = (step + 1) * 2 - 1;
}
System.out.println("初始步长 - " + step);
return step;
}
/**
* 测试
* @param args
*/
public static void main(String[] args) {
Integer[] intgArr = { 5, 9, 1, 4, 8, 2, 6, 3, 7, 10 };
ShelltSort<Integer> shellSort = new ShelltSort<Integer>();
Sort.testSort(shellSort, intgArr);
Sort.testSort(shellSort, null);
}
}
分享到:
相关推荐
用java对常用排序算法进行分析与实现.包含: 插入排序 直接插入排序、希尔排序 • 选择排序 简单选择排序、堆排序 • 交换排序 冒泡排序、快速排序 • 归并排序 • 基数排序
常用排序算法分析与实现(Java版),针对使用java代码编写
Java语言描述是国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。 系统地介绍各种常用的数据结构,对基本概念、...
这是一些常用的排序算法思想的分析和JAVA实现,还有具体的图解实例,简单明了,一看就会!
Java实现常用sorting算法,包括insertion, merge, bubble, heap, quick, couting, radix, bucket and maxHeap/Priority queue sorting。并对算法复杂度使用场景做了分析。 主要参考资料wikipedia, CLRS算法教材
JavaSwing常用算法 过程以及效率分析 支持扩展 请实现sort接口并继承baseSort父类,并在.properties文件进行配置。。 main函数在MFrame类里面。。 代码简陋, 望各位海涵
本项目主要使用Java实现各种经典常用数据结构及其算法,包括但不仅限于链表、栈,队列,树,图等经典数据结构。 八大排序算法及其实现,具体包括直接插入排序,希尔排序,直接选择排序,堆排序,冒泡排序,快速排序...
国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。系统地介绍各种常用的数据结构,对基本概念、基本原理和基本方法...
算法分析:通过数学方法分析算法的时间复杂度(运行时间随数据规模增长的速度)和空间复杂度(所需内存大小)来评估其效率。 学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、...
数值分析常用算法C++实现,并非所有。包括常微分、方程迭代求根、线性方程组直接求解、线性方程组迭代方程组求解、数值分析、插值。
Java语言描述(原书第3版)是国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。系统地介绍各种常用的数据结构,对...
该文档描述了使用Java语言实现常用算法,较为易读,适用于初学者
本文介绍了如何使用Java数组进行...通过对题目代码的分析和解决方案的说明,我们了解了每个操作的实现方法和作用。掌握这些数组操作和算法对于编写高效的Java程序非常重要,它们可以帮助我们处理不同类型的数据和问题。
主要介绍了Java求质数的几种常用算法,结合实例形式分析了三种比较常见的求质数算法原理及相关实现技巧,需要的朋友可以参考下
Java实现的常见排序算法_IT/计算机_专业资料。本文较为完整得收录了常用的排序算法以及其他事例,讲解详细,值得收藏学习!
util实现Java图片水印添加功能,有添加图片水印和文字水印,可以设置水印位置,透明度、设置对线段锯齿状边缘处理、水印图片的路径,水印一般格式是gif,png,这种图片可以设置透明度、水印旋转等,可以参考代码...
111页ppt详解了常用算法问题以及算法的实现,java版本