本文实例述说了PHP排序算法之归并排序(MergingSort)。分享给你们供你们参考，具体如下：
基本思想：
归并排序：就是借助归并（合并）的思想实现的排序方式。它的原理是假定初始序列富含n个元素，则可以看成是n个有序的子序列，每位子序列的宽度为1，之后两两归并，得到?n/2?（?x?表示不大于x的最小整数）个厚度为2或1的有序序列；再两两归并，······，这么重复，直到得到一个宽度为n的有序序列为止，这些排序方式就成为2路归并排序。
一、归并的过程：
a[i]取a字段的前部份（早已排好序），a[j]取a字段的后部份（早已排好序）
r链表储存排好序的a字段
比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，这般循环下去，直至其中一个有序表取完，之后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们一般用递归实现，先把待排序区间[s,t]以中点二分，接着把右边子区间排序，再把左边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
二、归并操作：
归并操作(merge)，也叫归并算法，指的是将两个次序序列合并成一个次序序列的技巧。
如设有数列{6，202，100，301，38，8，1}
初始状态：6,202,100,301,38,8，1
第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；
第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；
第三次归并后：{1,6,8,38,100,202,301},比较次数：4；
总的比较次数为：3+4+4=11,；
逆序数为14；
三、算法描述：
归并操作的工作原理如下：
第一步：申请空间，使其大小为两个早已排序序列之和，该空间拿来储存合并后的序列
第二步：设定两个表针，最初位置分别为两个早已排序序列的起始位置
第三步：比较两个表针所指向的元素，选择相对小的元素装入到合并空间，并联通表针到下一位置
重复步骤3直至某一表针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
算法实现：
我们先来瞧瞧主函数部份：
//交换函数functionswap(array&$arr,$a,$b){$temp=$arr[$a];$arr[$a]=$arr[$b];$arr[$b]=$temp;}//归并算法总函数functionMergeSort(array&$arr){$start=0;$end=count($arr)-1;MSort($arr,$start,$end);}
在总函数中，我们只调用了一个MSort()函数，由于我们要使用递归调用，所以将MSort()封装上去。
下边我们来瞧瞧MSort()函数：
functionMSort(array&$arr,$start,$end){//当子序列宽度为1时，$start==$end排序算法总结，不用再分组if($start<$end){$mid=floor(($start+$end)/2);//将$arr平分为$arr[$start-$mid]和$arr[$mid+1-$end]MSort($arr,$start,$mid);//将$arr[$start-$mid]归并为有序的$arr[$start-$mid]MSort($arr,$mid+1,$end);//将$arr[$mid+1-$end]归并为有序的$arr[$mid+1-$end]Merge($arr,$start,$mid,$end);//将$arr[$start-$mid]部份和$arr[$mid+1-$end]部份合并上去成为有序的$arr[$start-$end]}}
里面的MSort()函数实现将字段分半再分半（直至子序列宽度为1）排序算法总结，之后将子序列合并上去。
如今是我们的归并操作函数Merge():
//归并操作functionMerge(array&$arr,$start,$mid,$end){$i=$start;$j=$mid+1;$k=$start;$temparr=array();while($i!=$mid+1&&$j!=$end+1){if($arr[$i]>=$arr[$j]){$temparr[$k++]=$arr[$j++];}else{$temparr[$k++]=$arr[$i++];}}//将第一个子序列的剩余部份添加到早已排好序的$temparr字段中while($i!=$mid+1){$temparr[$k++]=$arr[$i++];}//将第二个子序列的剩余部份添加到早已排好序的$temparr字段中while($j!=$end+1){$temparr[$k++]=$arr[$j++];}for($i=$start;$iint(1)[1]=>int(2)[2]=>int(3)[3]=>int(4)[4]=>int(5)[5]=>int(6)[6]=>int(7)[7]=>int(8)[8]=>int(9)}
复杂度剖析：
因为归并算法无论原先的序列是否有序就会进行分组和比较，因而它的最好、最坏、平均的时间复杂度都是O(nlogn)。
归并算法是一种稳定的排序算法。
本文参考自《大话数据结构》，在此仅作记录，便捷之后查阅，前辈勿喷！
PS：这儿再为你们推荐一款关于排序的演示工具供你们参考：
在线动漫演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具：
更多关于PHP相关内容感兴趣的读者可查看本站专题：《php排序算法总结》、《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP字段(Array)操作方法大全》、《PHP常用遍历算法与方法总结》及《PHP物理运算方法总结》
希望本文所述对你们PHP程序设计有所帮助。
