数据结构和算法12 之希尔排序-阿里云开发者社区

开发者社区> shy丶gril> 正文

数据结构和算法12 之希尔排序

简介:
+关注继续查看

 上一章我们学习了冒泡排序、选择排序和插入排序三种基础排序算法,这三种排序算法比较简单,时间复杂度均为O(N2),效率不高。这节我们讨论一个高级排序算法:希尔排序。希尔排序是基于插入排序的,插入排序有个弊端,假设一个很小的数据项在很靠近右端的位置上,那么所有的中间数据项都必须向右移动一位,这个步骤对每一个数据项都执行了将近N次的复制,这也是插入排序效率为O(N2)的原因。

        希尔排序的中心思想是将数据进行分组,然后对每一组数据进行插入排序,在每一组数据都有序后,再对所有的分组利用插入排序进行最后一次排序。这样可以显著减少数据交换的次数,以达到加快排序速度的目的。

这种思想需要依赖一个增量序列,我们称为n-增量,n表示进行排序时数据项之间的间隔,习惯上用h表示。为了很好的理解增量排序,我们看下面的示意图:


        上图显示了增量为4时对10个数据项进行排序的示意图,一趟后0、4、8三个位置上的数据项已经排好序,接下来,算法向右移动一步,对1、5、9三个位置的数据项进行排序,这个过程一直持续进行,直到所有数据项都完成了一次4-增量排序,然后缩小增量,再重复上面的过程,最后一次增量为1,对所有的数据项进行一次插入排序,从而完成了希尔排序的全部步骤。因为最后一趟都已经基本有序了,所以复杂度没有向普通插入排序那么大了。

       说到这里,大家应该可以明白,增量序列在希尔排序中是很重要的。一般好的增量序列都有2个共同的特征:

        1. 最后一个增量必须为1,保证最后一趟是一次普通的插入排序;

        2. 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况

       这篇文章中我们使用增量序列用 h = 3 * h + 1来生成。h初值被赋予1,然后使用该公式生成序列1、4、13、40、121、364等等,当间隔大于数组大小的时候停止,使用序列的最大数组作为间隔开始希尔排序过程,然后没完成一次排序,用倒推公式 h = (h - 1) / 3来减小间隔,保证最后一次h=1,完成最后一次插入排序。

        说完了原理,下面看看具体实现代码:

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. public void shellSort2() {  
  2.     int h = 1;  
  3.     while(h <= nElem / 3) {  
  4.         h = h * 3 + 1//增量间隔  
  5.     }  
  6.       
  7.     while(h > 0) {  
  8.         for(int i = h; i < nElem; i++) {  
  9.             //每个增量间隔内,实现插入排序,两个for循环和插入排序一样,只不过第二个for循环里参数略有调整而已,和h有关  
  10.             for(int j = i; j < nElem; j += h) {  
  11.                 for(int k = j; (k - h >= 0) && a[k] < a[k - h]; k -= h) {  
  12.                     swap(k, k-h);  
  13.                 }  
  14.             }  
  15.         }  
  16.         h = (h-1) / 3;  
  17.     }  
  18. }  

        算法分析:希尔排序时间复杂度平均为O(NlogN),最好与最坏情况要根据具体的增量序列来判断,对于不同的增量序列有不同的复杂度。希尔排序的性能优于直接插入排序,因为在希尔排序开始时增量较大,分组较多,每组的记录数目少,故各组内直接插入较快,后来随着增量逐渐缩小,分组数逐渐减少,而各组的记录数目逐渐增多,但是由于已经局部排过序了,所以已经接近有序状态,新的一趟排序过程也较快。因此,希尔排序在效率上较直接插入排序有较大的改进。

        希尔排序是不稳定的,因为不同的间隔对应的数据是独自比较的,如果a=b,但是不在同一个间隔上,显然会出现前后颠倒的情况,所以希尔排序是不稳定的。

        空间复杂度为O(1),不需要额外的存储空间。

        希尔排序就介绍到这,如有错误之处,欢迎留言指正~+


转载:http://blog.csdn.net/eson_15/article/details/51168467

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
排序算法大数据量测试代码
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Collections; using System.Diagnostics; using System.IO; namespace Sort { class Program
812 0
python实现希尔排序算法
希尔排序是插入排序的一种又称“缩小增量排序”,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
1132 0
数据结构与算法之冒泡排序优化
冒泡排序优化 /** * 冒泡排序优化算法 * @param array */ public static void sort(int[] array) { int len = array.
483 0
怎么设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程
6835 0
解剖SQLSERVER 第二篇 对数据页面头进行逆向(译)
原文:解剖SQLSERVER 第二篇 对数据页面头进行逆向(译) 解剖SQLSERVER 第二篇  对数据页面头进行逆向(译) http://improve.dk/reverse-engineering-sql-server-page-headers/ 在开发OrcaMDF 的时候第一个挑战就...
634 0
使用OpenApi弹性释放和设置云服务器ECS释放
云服务器ECS的一个重要特性就是按需创建资源。您可以在业务高峰期按需弹性的自定义规则进行资源创建,在完成业务计算的时候释放资源。本篇将提供几个Tips帮助您更加容易和自动化的完成云服务器的释放和弹性设置。
7734 0
【最佳实践】运用 Logstash Fingerprint 过滤器处理并删除 Elasticsearch 重复数据
这篇文章介绍了使用 Logstash 在 Elasticsearch 中对数据进行重复数据删除的方法。 根据你的用例,Elasticsearch中 的重复内容可能不被接受。 例如,如果你要处理指标,则 Elasticsearch中 的重复数据可能会导致错误的聚合和不必要的警报。 即使对于某些搜索用例,重复的数据也可能导致不良的分析和搜索结果。
2546 0
+关注
1878
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载