本文介绍了Shell Sort的PHP排序算法。分享给大家参考，如下：

基本思想：

Hill排序是指按照目标的某个增量对记录进行分组，每组通过直接插入进行排序。随着增量逐渐减少，每组包含的关键词越来越多。当增量减少到1时，整个序列就被分成一组，算法终止。

操作步骤：

首先，取一个小于n(串行记录数)的整数d1作为第一个增量，将文件的所有记录分组。距离为d1倍数的所有记录都放在同一组中。首先，直接在每组中插入和排序；然后取第二个增量d2 d1，重复上述分组排序，直到增量dt=1(dt d(t-1) … d2 d1)，即所有记录放在同一个组中直接插入排序。

该方法本质上是一种分组插入方法

比较相隔很长一段距离的数字(称为增量)，使数字在移动时可以跨越多个元素，通过一次比较就可以消除多个元素的交换。1959年，D.L.shell在以他名字命名的排序算法中实现了这个想法。首先将一个待排序的组的编号按照一定的增量D分成若干组，每组记录的下标按D不同，将每组中的所有元素排序，然后按较小的增量排序，再按每组排序。当增量减为1时，将待排序的整数分成一组，排序完成。

一般第一次取序列的一半作为增量，然后每次减半，直到增量为1。

据说到现在还没有找到最佳增量序列，但是有一个很强的要求，最后一个增量值必须等于1。

给定实例的外壳排序的排序过程

假设文件中有10条记录需要排序，关键字为：

49,38,65,97,76,13,27,49,55,04。

增量序列的值如下：

5,3,1

算法实现：

？Php//Hill排序(直接插入排序的改进)函数shell排序(数组$ arr){ $ count=count($ arr)；$ inc=$ count//增量do {//计算增量//$ Inc=floor($ Inc/3)1；$inc=上限($ Inc/2)；for($ I=$ Inc；$ i $计数；$ I){ $ temp=$ arr[$ I]；//设置sentry//将$temp插入($j=$i-$inc)的有序增量子表中；$ j=0 $ arr[$ j $ Inc]$ arr[$ j]；$ j-=$ Inc){ $ arr[$ j $ Inc]=$ arr[$ j]；//记录向后移动}//插入$ arr[$ j $ Inc]=$ temp；}//当增量为1} while ($inc 1)时停止循环；}//$arr=array(9，1，5，8，3，7，4，6，2)；$arr=array(49，38，65，97，76，13，27，49，55，04)；ShellSort($ arr)；var _ dump($ arr)；运行结果：

数组(10){[0]=int(4)[1]=int(13)[2]=int(27)[3]=int(38)[4]=int(49)[5]=int(49)[6]=int(55)

通过以上代码的分析，相信大家都已经知道，Hill排序的关键不是随便分组后再排序，而是形成一个以一定“增量”分隔的记录子序列，从而实现跳跃运动，提高排序效率。

在最坏的情况下，时间复杂度为o (n 2)。

希尔排序是不稳定排序。

本文参考自《大话数据结构》。只记录在这里，方便以后参考。大神不应该喷！

PS:这里推荐一个排序的演示工具，供大家参考：

在线动画演示插入/选择/冒泡/合并/希尔/快速排序过程工具：http://tools.jb51.net/aideddesign/paixu_ys

更多对PHP相关内容感兴趣的读者可以查看本网站专题：《php排序算法总结》、《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》、《PHP数学运算技巧总结》、0103010

希望本文对PHP编程有所帮助。