PHP数据结构(二十一) ——希尔排序

PHP数据结构(二十一)——希尔排序

(原创内容,转载请注明来源,谢谢)

一、概述

希尔排序,又称缩小增量排序,也属于插入排序类方法,时间上有较大改进。前面叙述的插入排序方法的时间复杂度都是O(n2),当待排序记录都是正序时,时间复杂度提高到O(n)。

希尔排序的基本思想是:先将整个待排记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录基本有序时,再对全体进行一次插入排序。

二、算法

希尔排序实质上就是跳跃版的直接插入排序,其每次都设定一个不同的增量,如第一次增量是5、第二次增量是3,进行两轮插入排序后,最后再从头进行一次直接插入排序。

以第一次增量为5,第二次增量为3,数组长度为10举例,说明希尔排序算法。

1)把数组进行分组,因为增量是5,因此把下标048、159、26、37分别划分到各组,对每组依次进行直接插入排序,排序后每一组包含的数组下标还是原先的那几个数字(如048组进行插入排序,假设0对应的值大于4,则排序后下标变为408,不占用其他组的下标),排序后数组部分有序,此时称为完成一轮希尔排序。

2)以0369、147、258的下标值分组,分别对这三组值进行插入排序。此时称为完成第二轮希尔排序。

3)将前两轮排序后的数组,从头开始进行插入排序。

4)以此为拓展,可以输入一组增量数组,按照增量的值,依次进行分组的插入排序,最后再进行一次增量为1的插入排序。

三、实现源码

         //希尔排序 输入的第一个参数为增量数组,不用输入最终的增量1
         publicfunction shellInsertSort(array $arrIncr, array $arr = array()){
                   //如果增量数组长度小于1,直接调用直接插入排序即可
                   if(1> count($arrIncr)){
                            return$this->directInsertSort($arr);
                   }
                   $arr= $this->_checkNeedSort($arr);
                   if(!$arr){
                            return$arr;
                   }
                   //循环调用增量数组中的增量
                   foreach($arrIncras $incr){
                            //如果增量大于或等于数组长度,则直接取下一个增量
                            for($i=$incr;$i<count($arr);$i++){
                                     $tmp= $arr[$i];
                                     //以增量$incr的序列组成数组,同样假设前i-1个数有序,对第i个进插入排序
                                     for($j=$i-$incr;$j>=0&&$tmp<$arr[$j];$j=$j-$incr){
                                               $arr[$j+$incr]= $arr[$j];
                                     }
                                     $arr[$j+$incr]= $tmp;
                            }
                   }
                   //最后一组数组,调用直接插入排序,步长为1
                   $arr= $this->directInsertSort($arr);
                   return$arr;
         }       

四、评价

希尔排序的好坏,和选定的因子有非常大的关系,目前尚无定论哪种最好。但是经过大量的推导,当增量函数dlta[k]=2t-k+1-1时,时间复杂度为O(n3/2),其中t为排序的趟数,k的范围是1<=k<=t<=log2(n+1)(向下取整)。

增量函数的建议方法:

1)1,2,3,5,9…dlta[k]=2t-k+1 (0<=k<=t<= log2(n-1)(向下取整))

2)1,4,13,40…dlta[k]=(3t-k-1)/2 (0<=k<=t<= log2(2n+1)(向下取整))

增量函数要求:应使增量序列中的值没有除1以外的公因子,最终的增量值必须是1。

——written by linhxx 2017.07.18

相关阅读:

PHP数据结构(二十) ——其他插入排序

PHP数据结构(十九) ——B+树

PHP数据结构(十八) ——直接插入排序

PHP数据结构(十七) ——内部排序综述

PHP数据结构(十六) ——B树

PHP数据结构(十五) ——哈希表​

PHP数据结构(十四) ——键树(双链树)

PHP数据结构(十三) ——动态查找表(二叉排序树)

PHP数据结构(十二) ——静态查找表​

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(2)

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(1)

PHP数据结构(十) ——有向无环图与拓扑算法

PHP数据结构(九) ——图的定义、存储与两种方式遍历

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践2)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践1)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(理论)

PHP数据结构(七) ——串与实现KMP算法

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六) ——数组的相乘、广义表

PHP数据结构(五) ——数组的压缩与转置

PHP数据结构(四) ——队列

PHP数据结构(三)——运用栈实现括号匹配

PHP数据结构(二)——链式结构线性表

PHP数据结构(一)——顺序结构线性表

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-07-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python小屋

Python科学计算扩展库numpy中的广播运算

首先解答上一个文章Python扩展库numpy中的布尔运算中的问题,该题答案为[111, 33, 2],题中表达式的作用是按列表中元素转换为字符串后的长度降序排...

2668
来自专栏决胜机器学习

PHP数据结构(十七) ——内部排序综述

PHP数据结构(十七)——内部排序综述 (原创内容,转载请注明来源,谢谢) 一、稳定性 假设Ki=Kj(1<=i,j<=n,i!=j),且排在序列前的序列中R...

32412
来自专栏向治洪

算法笔记之排序

最近在看《算法笔记》,如果单从算法来说,这本书真正做到了短小精悍,首先以排序入题,那么我们今天也来说说排序。 排序 将一堆杂乱无章的元素按照某种规则有序排列的过...

20210
来自专栏软件开发 -- 分享 互助 成长

C++ 字符串分割

    java和C#中字符串都可以使用split进行分割,但是C++中却没有这个方法,之前总是自己写一个函数自己进行分割,倒也不麻烦,今天在网上找了类似的函数...

1816
来自专栏desperate633

LeetCode 34. Search for a Range题目分析代码

给定一个包含 n 个整数的排序数组,找出给定目标值 target 的起始和结束位置。

662
来自专栏专注 Java 基础分享

面试中常用排序算法实现(Java)

     当我们进行数据处理的时候,往往需要对数据进行查找操作,一个有序的数据集往往能够在高效的查找算法下快速得到结果。所以排序的效率就会显的十分重要,本篇我们...

2249
来自专栏PHP技术

PHP 排序算法实现讲解

所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。排序算法,就是如何使得记录按照要求排列的方法。排序 算法在很多领域得到相...

2695
来自专栏Albert陈凯

3.2 弹性分布式数据集

3.2 弹性分布式数据集 本节简单介绍RDD,并介绍RDD与分布式共享内存的异同。 3.2.1 RDD简介 在集群背后,有一个非常重要的分布式数据架构,即弹性...

34410
来自专栏Dawnzhang的开发者手册

数据结构与算法学习笔记之 从0编号的数组

数组看似简单,但掌握精髓的却没有多少;他既是编程语言中的数据类型,又是最基础的数据结构;

963
来自专栏决胜机器学习

PHP数据结构(二十五) ——并归排序

PHP数据结构(二十五)——并归排序 (原创内容,转载请注明来源,谢谢) 一、概述 并归排序是将两个或两个以上的有序表组合成一个新的有序表。采用并归的思想进...

3448

扫码关注云+社区