Shell(希尔)排序

Stella981
• 阅读 432

Shell(希尔)排序

    对于直接插入排序而言,如果一个很小的数据单元位于很靠近右端的位置上,为了把这个数据单元移动到左边正确的位置上,中间所有的数据单元都需要向右移动一格。这个步骤对每一个数据项都执行了近n次复制。虽然不是所有的数据项都必须移动n个位置,但平均下来,每个数据项都会移动n/2格,总共是n*n/2次复制。因此,直接插入排序的执行效率是O(n^2)[注:这里是n的平方]。

    Shell排序对直接插入排序进行了简单的改进:它通过加大插入排序中元素之间的间隔,并在这些有间隔的元素中进行插入排序,从而使数据项大跨度地移动,当这些数据项经过一趟排序之后。Shell排序算法减少数据项的间隔再进行排序,依次进行下去。这些进行排序的数据项之间的间隔被称为增量,习惯上用h来表示这个增量,并且满足以下公式 :

                       h = 3*h+1反过来 h = (h-1)/3

    当h值很大的时候,数据项每一趟排序需要移动元素的个数非常少,但数据项移动的距离非常长,这是非常有效率的。当h减少时,每一趟排序需要移动的元素个数增多,但此时数据项已经接近于它们排序后最终的位置,这对于插入排序可以更有效率。(直接使用增量为1的Shell排序就是直接插入排序

Shell排序的实现

    /**
     * Shell(希尔)排序
     * @param data 待排序数组
     */
    public static void shellSort(int[] data){
        //先求增量
        int h = 1;
        //按 3*h+1 得到最大的增量
        while(h <= data.length/3){
            h = 3*h+1;
        }
        while(h > 0){
            for(int i = h; i<data.length; i++){
                //i索引处的值已经比前面的所有值都大,表明已经有序,无序插入
                //(i-h 索引之前的数据已经有序,i-h索引处的元素的值就是最大值)
                if(data[i-h] > data[i]){
                    //当数据整体后移时,保证data[i]处的元素不丢失
                    int temp = data[i];
                    //最多后移多少个元素
                    int j = i-h;
                    //循环判断,只要前面的元素比data[i]大,则需要后移,注意这里是j-=h而不是j--
                    for(;j>=0 && data[j] > temp; j-=h){
                        data[j+h] = data[j];
                    }
                    //最后将temp插入到合适的位置
                    data[j+h] = temp;
                }
            }
            //依据增量公式,计算下一个增量
            h = (h-1)/3;
        }
    }

测试代码

Shell(希尔)排序  

算法分析

(1)时间复杂度:O(n^3/2)~O(n^7/6)

(2)空间复杂度::O(1)

(3)Shell排序是不稳定的

(4)只能用于顺序结构,不能用于链式结构

(5)记录总的比较次数和移动次数都比直接插入排序要少,n越大时,效果越明显。所以适合初始记录无序,n较大时的情况。

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Jacquelyn38 Jacquelyn38
2年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Wesley13 Wesley13
2年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Stella981 Stella981
2年前
JS 对象数组Array 根据对象object key的值排序sort,很风骚哦
有个js对象数组varary\{id:1,name:"b"},{id:2,name:"b"}\需求是根据name或者id的值来排序,这里有个风骚的函数函数定义:function keysrt(key,desc) {  return function(a,b){    return desc ? ~~(ak
Wesley13 Wesley13
2年前
PHP创建多级树型结构
<!lang:php<?php$areaarray(array('id'1,'pid'0,'name''中国'),array('id'5,'pid'0,'name''美国'),array('id'2,'pid'1,'name''吉林'),array('id'4,'pid'2,'n
Wesley13 Wesley13
2年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
2年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
1个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这