liukuan.net

liukuan.net,发现,记录,分享

191

PHP排序之-归并排序

和快速排序不同的是,归并是在合并的过程中实现排序,通过两两合并的过程,达到排序的目的。
比如数组 1,5,0,-30,52,10,100 最终排序的过程会被拆分成两两合并, 【 1,5】 【0,-30】 【52,10】 100
下一步会在上一步的基础上再两两合并
function merge(&$arr,$start,$mid,$end) {
$i = $start;
$j = $mid+1;
$k = 0;
$ary = array();
while($i <= $mid && $j <= $end) {
if($arr[$i] <= $arr[$j]) {
$ary[$k++] = $arr[$i++];
} else {
$ary[$k++] = $arr[$j++];
}
}
while($i <= $mid) {
$ary[$k++] = $arr[$i++];
}
while($j <= $end) {
$ary[$k++] = $arr[$j++];
}
for($i = 0 ;$i < $k;$i++) {
$arr[$i + $start] = $ary[$i];
}
}
function merge_sort(&$array,$low,$high) {
if($low < $high) { // 任何递归都要有边界,否则就是死循环
$mid = floor(($low+$high) / 2);
merge_sort($array,$low,$mid);
merge_sort($array,$mid+1,$high);
merge($array,$low,$mid,$high);
} else {
return ;// 这里其实可以不写,php内部默认都会自动加return的
}
}

原文地址 : https://liukuan.net/php/98.html
本站遵循 : 知识共享署名-非商业性使用-相同方式共享 3.0 版权协议
版权声明 : 原创文章转载时,请务必以超链接形式标明 文章原始出处
作者:admin | 分类:php | 标签: php
此文章共有条评论, 人参与 |Powerd By Angboo