希尔排序
希尔排序(Shell’s Sort)又称“缩小增量排序”(Diminishing Increment Sort),它也是一种属于插入排序类的方法,但在时间效率上比直接插入排序方法有较大的改进。
从对直接插入排序的分析得知,其算法时间复杂度为O(n2),但是,若待排记录序列为“正序”时,其时间复杂度可提高至O(n),由此可设想,若待排记录序列按关键字“基本有序”,直接插入排序的效率就可以大大提高。从另一方面来看,由于直接插入排序算法简单,所以在n值很小时效率比较高。希尔排序正是从这两点分析出发对直接插入排序进行改进而得到的一种插入排序方法。
希尔排序的基本思想是:先将整个待排序列分割成若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序。(这是《数据结构》这本书里的说法。)
我觉得更好的一种说法是:先取较大的步长对待排序列进行直接插入排序,每排一次就缩小一次步长,再进行插入排序,直到最后步长变为1。
希尔排序实例
将序列 49、38、65、97、76、13、27、49、55、4 用 shell 排序的方法进行排序:
1.选定步长序列,如选为 8、4、2、1
2.针对步长序列进行排序,从最大的步长开始,逐步减少步长,最后一次选择的的步长肯定为1。
性能分析
希尔排序的分析是一个复杂的问题,因为和增量序列的选取有关。通常可认为时间复杂性为O(n1.3)或 O(n1.25)。
程序代码
假设增量序列的取法是:第一次取n/2,之后每次都除2,直到1为止。
并且假设数组元素为整型,并且记录本身就为关键字,得到希尔排序的代码如下:(输入为数组和其元素个数)
typedef int ElemType; void ShellSort(ElemType A[],int n) { ElemType x; int i,j,d; for(d=n/2;d>=1;d/=2) { for(i=d;i<n;++i) { x=A[i]; j=i-d; while(A[j]>x) { A[j+d]=A[j]; j-=d; } A[j+d]=x; } } }
相关推荐
合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序的C语言实现,原创。
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
本实验含有四部分内容——直接插入排序、希尔排序、选择排序、快速排序,在上述内容的基础上,将所有排序算法整合在一个程序中。学生可参考教材中的伪代码。鼓励学生自创新思路,新算法。
六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。包含实验报告和源代码设计。
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
数据结构 综合排序 冒泡排序 直接插入排序 快速排序 希尔排序,完整的代码,有每种排序时间的比较
10种排序算法代码+综合比较代码(直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序、折半插入排序、2路插入排序),其中不仅有各种排序算法的代码,还包含10种代码在关键字...
各种基本排序方法(直接插入、希尔、直接选择、冒泡、快速、堆、二路归并)的大致原理和过程、复杂性和稳定性、相应算法的程序段;
冒泡排序、选择排序、插入排序和希尔排序 冒泡排序、选择排序、插入排序和希尔排序 冒泡排序、选择排序、插入排序和希尔排序
直接插入排序、折半插入排序、希尔排列
插入排序之希尔排序
C# 排序算法大全参考资料,比较清淅的一个版本。集中介绍了C#中的冒泡算法、选择排序、插入排序、希尔排序等常用算法,并包含示例代码和注意事项等。
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht
直接插入排序、希尔排序、冒泡排序、直接选择排序、堆排序、归并排序
本文介绍了C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序 冒泡排序、选择排序、插入排序和希尔排序
c++实现的线性表排序算法 插入排序,希尔排序,冒泡排序,快速排序,堆排序,归并排序等
插入排序采用三种方法实现,希尔排序根据插入排序采用的方法不同,也有三种,但是又通过改进得到一种最为简介的实现方式。所有方法的实现在博客中:http://blog.csdn.net/ns_code/article/details/20043459中有详细...
插入排序,希尔排序,C程序代码,经过运行,决定可用
希尔排序法,最经典的排序法,但不是容易懂。包括希尔插入排序,希尔交换排序