1、基本思想
先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。
2、图示
3、Java代码实现
package com.leiht.sort;
/**
* 希尔排序算法简单实现
* @author Leiht
*
*/
public class ShellSort {
public static void main(String[] args) {
int[] numbers = { 56, 45, 78, 67, 99, 13, 34, 49, 55, 34, 12, 77, 1 };
System.out.println("排序之前:");
for (int i = 0; i < numbers.length; i++) {
System.out.print(numbers[i] + " ");
}
//执行排序算法
new ShellSort().sort(numbers);
System.out.println();
System.out.println("排序之后:");
for (int i = 0; i < numbers.length; i++) {
System.out.print(numbers[i] + " ");
}
}
/**
* 排序方法
*
* @param numbers
*/
public void sort(int[] numbers) {
//定义分组1 d2 d3 ....dn dn= numbers.length / 2;
//目前效率较高的d的定义为 1,3 ,5. ... 2的K次方-1
int d = numbers.length / 2;
while (true) {
//每次 d = d /2
d = d / 2;
//第一次循环次数为0到d 代表总共分组的组数(一共有多少组)
for (int index = 0; index < d;index++) {
//循环第一组,增量为d,即【第i个,i+d, i+2d, i+3d....】为一组
//并按照直接插入排序对第一组进行排序,直到d=1,即对其完成直接排序
for (int i = index + d; i < numbers.length; i = i + d) {
int temp = numbers[i];
int j;
//循环从当前数据的前一个开始(如大于当前数据则向后移动一位即if(numbers[j] > temp) numbers[j + d] = numbers[j];)
//到有小于或等于当前数据止,跳出循环,将当前数据放到该位置即numbers[j + d] = temp;
for (j = i - d; j >= 0; j = j - d) {
if(numbers[j] > temp) {
numbers[j + d] = numbers[j];
}else {
break;
}
}
numbers[j + d] = temp;
}
}
if (d == 1) {
break;
}
}
}
}
4、分析
前面分析过插入排序是稳定的,但经过多次插入排序后相同的元素的位置已经发生移动,最后稳定性会被打乱,所以希尔排序算法的实现是不稳定的。
- 大小: 75 KB
分享到:
相关推荐
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
七种排序算法(包括直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,简单选择排序,归并排序) 还有两道题 1./*设计并实现一个有效的对n个整数重排的算法,使得所有负数位于非负数之前,给出算法的性能...
主要介绍了Python实现希尔排序算法,简单讲述了希尔排序的原理并结合具体实例形式分析了Python希尔排序的具体实现方法与使用技巧,需要的朋友可以参考下
主要介绍了基于JavaScript实现的希尔排序算法,简单分析了希尔排序的原理并结合实例形式给出了javascript实现希尔排序的操作步骤与相关注意事项,需要的朋友可以参考下
用java对常用排序算法进行分析与实现.包含: 插入排序 直接插入排序、希尔排序 • 选择排序 简单选择排序、堆排序 • 交换排序 冒泡排序、快速排序 • 归并排序 • 基数排序
主要介绍了php实现希尔排序算法的方法,简单说明了希尔排序的原理,并结合实例形式分析了php实现希尔排序的具体操作技巧,需要的朋友可以参考下
主要介绍了Python排序搜索基本算法之希尔排序,简单说明了希尔排序的原理并结合实例形式分析了Python实现希尔排序的具体操作技巧,需要的朋友可以参考下
通过实验,帮助学生由浅入深地掌握各种简单排序和高级排序的基本思想,让他们比较其性能,也让他们更好地理解希尔排序和快速排序的方法。 1.任意输入一个数组并利用简单选择排序算法对此数组的元素按从大到小的顺序...
希尔排序和链式基数排序;起泡排序,快速排序,归并排序;简单选择排序,树形选择排序和堆排序。 通过输入不同的数据量和数据大小正序,逆序和乱序情况比较各种排序算法的效率。 其中树形选择排序算法有点错误。
(2)需要实现起泡排序(Bubble)、直接插入排序(Insert)、简单选择排序(Select)、快速排序(Quick)、希尔排序(Shell)、堆排序(Heap)几种基本排序算法。 (3)需要实现数据的插入操作,将五组数据存入...
直接选择排序,希尔排序,直接插入排序,设计算法实现树形选择排序,要求能用数组和树来演示排序过程,以清晰地表示出排序过程,以数组和二叉树形式动态演示堆排序算法过程
实现各排序算法,必须实现起泡排序、希尔排序和简单选择排序,其他排序算法选做,并分析各算法的性能。
对以下常用的内部排序算法进行比较:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 [测试数据] 由随机产生器决定。 [实现提示] 待排序表的表长不少于100;其中的数据要用伪随机数产生...
设计要求:(1)要求实现起(冒)泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序以及2路归并排序算法。设计良好的功能界面。(2)要求待排序的元素的关键字为整数。其中的数据要用伪随机产生程序...
⑴ 编程实现内部排序算法:编程实现直接插入排序,希尔排序,冒泡排序,快速排序,简单选择排序,堆排序,归并排序算法。 ⑵ 要求数据规模:待排序数据类型不限(整型或浮点型),读取自磁盘文件。需用多组、多规模...
对直接插入排序、希尔排序、冒泡排序、快排、简单选择排序、堆排序的性能进行分析:比较各种排序算法在不同测试数据情况下的比较次数、移动次数。
希尔排序时效分析很难,关键码的比较次数与记录移动次数依赖于增量因子序列d的选取,特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以...
b) 希尔排序; c) 冒泡排序; d) 快速排序; e) 简单选择排序; f) 堆排序; g) 归并排序; h) 基数排序(选作); i) 其他; 具体要求如下: a) 测试数据分出三类:正序,逆序,随机数据; b) 对于这三类数据,比较...
七种排序算法(包括直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,简单选择排序,归并排序) 还有两道题 1./*设计并实现一个有效的对n个整数重排的算法,使得所有负数位于非负数之前,给出算法的...