希尔排序是插入排序算法的一种。又称 缩小增量排序
算法思想:
对于n个整数排序,将这列数按d1增量分组,对各个分组进行直接插入排序,然后缩小增量,重新分组,对分组排序,直到增量值为1时停止。
优劣
不需要大量的辅助空间,和归并排序一样容易实现。
希尔排序是基于插入排序的一种算法,
在此算法基础之上增加了一个新的特性,提高了效率。
希尔排序的时间复杂度为 O(N*(logN)2), 没有快速排序算法快
O(N*(logN)),因此中等大小规模表现良好,对规模非常大的数据排序不是
最优选择。但是比O(N2)复杂度的算法快得多。并且希尔排序非常容易实现,算法代码短而简单。
此外,希尔算法在最坏的情况下和平均情况下执行效率相差不是很多,与此同时快速排序在最坏 的情况下执行的效率会非常差。
专家门提倡,几乎任何排序工作在开始时都可以用希尔排序,若在实际使用中证明它不够快, 再改成快速排序这样更高级的排序算法.
本质上讲,希尔排序算法的一种改进,减少了其复制的次数,速度要快很多。
原因是,当N值很大时数据项每一趟排序需要的个数很少,但数据项的距离很长。
当N值减小时每一趟需要和动的数据增多,此时已经接近于它们排序后的最终位置。 正是这两种情况的结合才使希尔排序效率比插入排序高很多。
当n较大时,比较和移动的次数约在nl.25到1.6n1.25之间。
不稳定
//希尔排序
public static int[] xerSort(int _d[]){
int len = _d.length; //数组长度
//r为结果数组
int r[] = new int[len];
int d = len/2; //增量
while(d >= 1){
int j = 0;
/********分组插入排序部分***********/
for(int i = 0; i < len; i = i+d){
//j为结果数组中最后一个元素的位置,初始为负值,直接放入 结果数组
j = i-d;
int key = _d[i];
//从右往左依次比较移动元素,若比需插入的元素大,向后移动,否则插入结果数组
while(j >= 0 && r[j] > key){
r[j+d] = r[j];
j = j-d;
}
r[j+d] = key;
}
/********分组插入排序结束***********/
d = d/2;
}
return r;
}
分享到:
相关推荐
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
一个数据结构作业,对刚刚学习希尔排序知识的同学有用,用C++做的
合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序的C语言实现,原创。
希尔排序 希尔排序希尔排序希尔排序希尔排序希尔排序希尔排序希尔排序
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
希尔排序的源代码; 平台:CentOS release 5.4 (Final) 编译器:GCC 4.3.2
用C++,模板写的 7中排序. 快速排序, 归并排序,插入排序,选择排序,起泡排序,堆排序,希尔排序
数据结构 综合排序 冒泡排序 直接插入排序 快速排序 希尔排序,完整的代码,有每种排序时间的比较
此希尔排序算法采用增量减半的方法来进行数据的排序,内有部分注释
排序算法: 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序
1) 至少采用三种方法实现上述问题求解(提示,可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序)。并把排序后的结果保存在不同的文件中。 2) 统计每一种排序方法的性能(以上机...
希尔排序法,最经典的排序法,但不是容易懂。包括希尔插入排序,希尔交换排序
排序算法很多,下面有基数排序,堆排序,希尔排序,直接插入排序的代码和思路
本实验含有四部分内容——直接插入排序、希尔排序、选择排序、快速排序,在上述内容的基础上,将所有排序算法整合在一个程序中。学生可参考教材中的伪代码。鼓励学生自创新思路,新算法。
就利用汇编版的希尔排序来写了一下超级列表框排序.发现,从取值-排序-显示过程才花了1秒的时间.速度是七号排序的30倍,凌晨孤星-超级列表框排序的3倍.而这个希尔排序模块.只用增加,删减自定义数据类型成员.即可变身另...
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
希尔排序,堆排序,快速排序,简单选择排序,插入排序,冒泡排序
插入排序之希尔排序
了解冒泡,选择,插入,希尔排序 基本的渐进分析
希尔排序(程序).txt希尔排序(程序).txt希尔排序(程序).txt