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 条评论
登录 后参与评论

相关文章

来自专栏数说戏聊

SUBSTRING() 与 CONV() 函数1.substring()函数2.conv()函数

MySQL 字符串截取函数:left(), right(), substring(), substring_index()。

812
来自专栏恰同学骚年

《C#图解教程》读书笔记之三:方法

    不为形参在栈上分配内存,形参的参数名作为实参变量的别名指向同一位置,必须使用ref关键字,并且事先需要被赋值;

762
来自专栏数据库新发现

php中几个字符处理函数的说明

使用字符串 dellimiter 把 data 分割成一个数组返回 类似函数:split()

922
来自专栏企鹅号快讯

JAVA核心技术学习笔记

掌握Java核心技术是学习和掌握好Java技术的关键,下边分17个点对这些Java核心技术进行讲解。 >>>1.Java中没有多继承,而是用接口来代替多继承 >...

1875
来自专栏决胜机器学习

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

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

3838
来自专栏五分钟学算法

五分钟学会一个有意思的排序:计数排序

由于LeetCode上的算法题很多涉及到一些基础的数据结构,为了更好的理解后续更新的一些复杂题目的动画,推出一个新系列 -----《图解数据结构》,主要使用动画...

966
来自专栏顶级程序员

说出来你们可能不信,但是数组名确实不是指针常量

这篇是一篇C语言劝退流教学文,看不懂的同学应该是劝退教学流的目标对象 (写完了才想起来注一下,本文提到的“数组”和“数组名”字样,指的是数组左值表达式(arr...

3666
来自专栏沈唁志

PHP中系统函数http_build_query系统函数使用方法

1614
来自专栏张俊红

python中的小魔法(一)

? 总第101篇 if-else的简洁写法 #常规写法 if a>b: c=a else: c=b #简洁写法 c=a if a>b...

2674
来自专栏机器学习算法与Python学习

python基础语法(1)

从今天起,将进行python的一个系列学习,从基本的语法学起,后期会推出一些关于web开发,网络爬虫以及用python的第三方库进行数据挖掘与机器学习等高级的开...

37414

扫码关注云+社区