文档章节

希尔排序详解

fengsehng
 fengsehng
发布于 2016/11/09 09:11
字数 1022
阅读 1
收藏 0

【推荐】2019 Java 开发者跳槽指南.pdf(吐血整理) >>>

概述

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

1.插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率。

2.但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。

基本思想

先取一个小于n的整数d1作为第一个增量,把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2

代码

public static void main(String [] args)
{
    int[]a={49,38,65,97,76,13,27,49,78,34,12,64,1};
        System.out.println("排序之前:");
        for(int i=0;i<a.length;i++)
        {
            System.out.print(a[i]+" ");
        }
        //希尔排序
        int d=a.length;
            while(true){
            for(int i=0;i<d;i++){
                for(int j=i;j+d<a.length;j+=d){
                int temp;
                if(a[j]>a[j+d]){
                    temp=a[j];
                    a[j]=a[j+d];
                    a[j+d]=temp;
                    }
                }
            }


            if(d==1){break;}
            d--;
           }
            System.out.println();
            System.out.println("排序之后:");
                for(int i=0;i<a.length;i++)
                {
                    System.out.print(a[i]+" ");
                }
    }

时间复杂度

不需要大量的辅助空间,和归并排序一样容易实现。希尔排序是基于插入排序的一种算法, 在此算法基础之上增加了一个新的特性,提高了效率。希尔排序的时间复杂度与增量序列的选取有关,例如希尔增量时间复杂度为O(n²),而Hibbard增量的希尔排序的时间复杂度为O( ),希尔排序时间复杂度的下界是n*log2n。希尔排序没有快速排序算法快 O(n(logn)),因此中等大小规模表现良好,对规模非常大的数据排序不是最优选择。但是比O( )复杂度的算法快得多。并且希尔排序非常容易实现,算法代码短而简单。 此外,希尔算法在最坏的情况下和平均情况下执行效率相差不是很多,与此同时快速排序在最坏的情况下执行的效率会非常差。专家们提倡,几乎任何排序工作在开始时都可以用希尔排序,若在实际使用中证明它不够快,再改成快速排序这样更高级的排序算法. 本质上讲,希尔排序算法是直接插入排序算法的一种改进,减少了其复制的次数,速度要快很多。 原因是,当n值很大时数据项每一趟排序需要的个数很少,但数据项的距离很长。当n值减小时每一趟需要和动的数据增多,此时已经接近于它们排序后的最终位置。 正是这两种情况的结合才使希尔排序效率比插入排序高很多。Shell算法的性能与所选取的分组长度序列有很大关系。只对特定的待排序记录序列,可以准确地估算关键词的比较次数和对象移动次数。想要弄清关键词比较次数和记录移动次数与增量选择之间的关系,并给出完整的数学分析,至今仍然是数学难题。

稳定性

不稳定

我的微信二维码如下,欢迎交流讨论

这里写图片描述

欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧

微信订阅号二维码如下:

这里写图片描述

© 著作权归作者所有

fengsehng
粉丝 4
博文 284
码字总数 214494
作品 0
朝阳
程序员
私信 提问
插入排序,希尔排序,堆排序详解

本文将介绍三种排序算法--插入排序,希尔排序,堆排序。本文所有例子都是使用升序 一.插入排序 算法思想 维护一个有序数组,将要插入的数据与有序数组自最后一个元素直到合适位置的数一一比较...

crazys_蘑菇
2018/06/29
0
0
Java数据结构与算法(六)-希尔排序

一、希尔排序的产生 希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名...

FantJ
2017/12/21
0
0
《数据结构与算法系列》合集整理

《数据结构与算法系列》合集整理 整理来自博客园skywang12345,以下摘自作者介绍: “最近抽空整理了"数据结构和算法"的相关文章。在整理过程中,对于每种数据结构和算法分别给出"C"、"C++"...

kaixin_code
2018/12/01
232
0
【译】Swift算法俱乐部-希尔排序

本文是对 Swift Algorithm Club 翻译的一篇文章。 Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目,目前在GitHub上有18000+⭐️,我初略统计了一下...

Andy_Ron
2018/11/05
0
0
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

nginx反向代理+负载均衡+服务器宕机解决办法

反向代理 作用:保证系统安全,不暴露服务器IP,利用nginx服务器,利用内网ip进行访问,避免出现攻击服务器的情况 启动本地tomact,127.0.0.1:8080可以访问到tomcat管理页面 效果:通过 bbs....

Jack088
4分钟前
1
0
返回IEnumerable 与IQueryable相比 [关闭]

返回IQueryable<T>与IEnumerable<T>之间有什么区别? IQueryable<Customer> custs = from c in db.Customerswhere c.City == "<City>"select c;IEnumerable<Customer> custs = from c i......

技术盛宴
11分钟前
2
0
开放下载 | 《Knative 云原生应用开发指南》开启云原生时代 Serverless 之门

点击下载《Knative 云原生应用开发指南》 自 2018 年 Knative 项目开源后,就得到了广大开发者的密切关注。Knative 在 Kubernetes 之上提供了一套完整的应用 Serverless 编排服务,让应用开发...

阿里巴巴云原生
15分钟前
2
0
解密淘宝推荐实战,打造 “比你还懂你” 的个性化APP

手淘推荐简介 手淘推荐的快速发展源于2014年阿里“All in 无线”战略的提出。在无线时代,手机屏幕变小,用户无法同时浏览多个视窗,交互变得困难,在这样的情况下,手淘借助个性化推荐来提升...

阿里云官方博客
18分钟前
2
0
内核程序中进程的pid,handle,eprocess之间相互转换的方法

在内核程序开发中,我们常常需要取得某进程的pid或句柄,或者需要检索进程的eprocess结构,很多API函数需要的参数也不同,所以掌握pid<->handle<->eprocess相互转换的方法会大大提高我们的开...

simpower
20分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部