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

相关文章

来自专栏编程

《4》python数据类型和变量

(4)python数据类型和变量 ? 整数 Python可以处理任意大小的整数,例如:1,100,-8080,0,等等。 十六进制用0x前缀和0-9,a-f表示...

3259
来自专栏小詹同学

Leetcode打卡 | No.21 合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

661
来自专栏lgp20151222

排序算法对比,步骤,改进,java代码实现

发现是时候总结一番算法,基本类型的增删改查的性能对比,集合的串并性能的特性,死记太傻了,所以还是写在代码里,NO BB,SHOW ME THE CODE!

482
来自专栏我和PYTHON有个约会

32.企业级开发进阶4:正则表达式

本节内容,要讲解的和我们的信息检索有关系,这一方面也是Python在目前非常流行的一个应用方向:爬虫。

681
来自专栏阿凯的Excel

Python读书笔记13(初识字典)

今天和大家分享的是字典~ 字典是使用频率仅次于列表,部分应用使用频率其实比列表还要多。 字典是虾米呢?先看一下长什么样子~ ? 不好意思~拿错图了~ ? ...

3407
来自专栏决胜机器学习

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

PHP数据结构(十六)——B树 (原创内容,转载请注明来源,谢谢) 一、概述 B树在很多地方被称为“B-树”,因为B树的原英文名称为B-tre...

41511
来自专栏Android机器圈

递归 —— 二分查找法 —— 归并排序

二分法就是把一个数组折半查找,再折半直到找到数据位置,或者无数据位置。比如说1-100,你选的值是23,那么范围写法就是(索引写法类似)

1204
来自专栏决胜机器学习

PHP数据结构(二十四) ——堆排序

PHP数据结构(二十四)——堆排序 (原创内容,转载请注明来源,谢谢) 一、定义 堆排序也属于一种选择排序,效率较高且空间占用相对较少。 堆的定义:n个元...

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

python基础-字符串与编码

转载于:廖雪峰的官方网站-python教程 字符编码 我们已经讲过了,字符串也是一种数据类型,但是,字符串比较特殊的是还有一个编码问题。 因为计算机只能处理数字...

43711
来自专栏极客猴

Python中“is”和“==”的区别

相比 C/C++ 、Java 等强类型语言, Python 定义变量的方式就简单多了。我们只需要给变量起个变量名,而不需要给变量指定类型。

662

扫描关注云+社区