数据结构与算法分析 写道
/*希尔排序(Shell Sort)是插入排序的一种。其基本思想是:先取定一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1
* 个组,所有距离为d1的倍数的记录放在同一个组中,在各个组中进行插入排序;然后,取第二个增量d2<d1,重复上述的分组和排序,
* 直至所取的增量dt=1(dt<dt-1<...<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
* new int[]{8,5,1,7,9,4,6},开始分割集合的间隔长度为3的情况,[[6][3][0]比较排序后,[4]和[1]比较排序后,[5]和[2]比较排序后,
* 分割集合的间隔长度为1,这时[1]和[0]比较排序后,[2][1][0]....,和直接插入排序一样了。*/
public static void shellSort(int[] intArray) {
System.out.print("将要排序的数组为: ");
for(int k=0;k<intArray.length;k++)
System.out.print(" "+intArray[k]+" ");
System.out.println();
int arrayLength=intArray.length;
int j,k;//循环变量
int temp;//暂存变量
boolean isChange;//数据是否改变
int dataLength;//分割集合的间隔长度
int pointer;//进行处理的位置
dataLength=arrayLength/2;//初始集合间隔长度
while(dataLength!=0){//数列仍可进行分割
//对各个集合进行处理
for(j=dataLength;j<arrayLength;j++){
isChange=false;
temp=intArray[j];//暂存,待交换值时用
pointer=j-dataLength;//计算进行处理的位置
//进行集合内数值的比较与交换值
while(temp<intArray[pointer]&&pointer>=0&&pointer<arrayLength){
intArray[pointer+dataLength]=intArray[pointer];
//计算下一个欲进行处理的位置
pointer=pointer-dataLength;
isChange=true;
System.out.print("every changing result: ");
for(k=0;k<arrayLength;k++)
System.out.print(" "+intArray[k]+" ");
System.out.println();
if(pointer<0||pointer>arrayLength)
break;
}
//与最后的数值交换
intArray[pointer+dataLength]=temp;
if(isChange){
System.out.print("Current sorting result: ");
for(k=0;k<arrayLength;k++)
System.out.print(" "+intArray[k]+" ");
System.out.println();
}
}
System.out.print("指定分割集合的间隔长度为"+dataLength+",对各个集合进行处理后,Current sorting result: ");
for(k=0;k<arrayLength;k++)
System.out.print(" "+intArray[k]+" ");
System.out.println();
dataLength=dataLength/2;//计算下次分割的间隔长度
}
}
运行后的结果为:
将要排序的数组为: 8 5 1 7 9 4 6
every changing result: 8 5 1 8 9 4 6
Current sorting result: 7 5 1 8 9 4 6
every changing result: 7 5 1 8 9 4 8
every changing result: 7 5 1 7 9 4 8
Current sorting result: 6 5 1 7 9 4 8
指定分割集合的间隔长度为3,对各个集合进行处理后,Current sorting result: 6 5 1 7 9 4 8
every changing result: 6 6 1 7 9 4 8
Current sorting result: 5 6 1 7 9 4 8
every changing result: 5 6 6 7 9 4 8
every changing result: 5 5 6 7 9 4 8
Current sorting result: 1 5 6 7 9 4 8
every changing result: 1 5 6 7 9 9 8
every changing result: 1 5 6 7 7 9 8
every changing result: 1 5 6 6 7 9 8
every changing result: 1 5 5 6 7 9 8
Current sorting result: 1 4 5 6 7 9 8
every changing result: 1 4 5 6 7 9 9
Current sorting result: 1 4 5 6 7 8 9
指定分割集合的间隔长度为1,对各个集合进行处理后,Current sorting result: 1 4 5 6 7 8 9
当分割的间隔为1时,变成了直接插入排序。
分享到:
相关推荐
插入排序之希尔排序
合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序的C语言实现,原创。
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
本实验含有四部分内容——直接插入排序、希尔排序、选择排序、快速排序,在上述内容的基础上,将所有排序算法整合在一个程序中。学生可参考教材中的伪代码。鼓励学生自创新思路,新算法。
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。包含实验报告和源代码设计。
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
数据结构 综合排序 冒泡排序 直接插入排序 快速排序 希尔排序,完整的代码,有每种排序时间的比较
10种排序算法代码+综合比较代码(直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序、折半插入排序、2路插入排序),其中不仅有各种排序算法的代码,还包含10种代码在关键字...
各种基本排序方法(直接插入、希尔、直接选择、冒泡、快速、堆、二路归并)的大致原理和过程、复杂性和稳定性、相应算法的程序段;
冒泡排序、选择排序、插入排序和希尔排序 冒泡排序、选择排序、插入排序和希尔排序 冒泡排序、选择排序、插入排序和希尔排序
直接插入排序、折半插入排序、希尔排列
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht
直接插入排序、希尔排序、冒泡排序、直接选择排序、堆排序、归并排序
C# 排序算法大全参考资料,比较清淅的一个版本。集中介绍了C#中的冒泡算法、选择排序、插入排序、希尔排序等常用算法,并包含示例代码和注意事项等。
主要介绍了Java 插入排序之希尔排序的实例的相关资料,需要的朋友可以参考下
用C++,模板写的 7中排序. 快速排序, 归并排序,插入排序,选择排序,起泡排序,堆排序,希尔排序
本文介绍了C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序 冒泡排序、选择排序、插入排序和希尔排序
c++实现的线性表排序算法 插入排序,希尔排序,冒泡排序,快速排序,堆排序,归并排序等
希尔排序法,最经典的排序法,但不是容易懂。包括希尔插入排序,希尔交换排序