[PHP]算法-归并排序的PHP实现

<div class="cnblogs_Highlighter">
<pre class="brush:php;gutter:true;"><?php
//归并排序

function merge(&$A,$left,$mid,$right,$temp){
//7.左堆起始
$i=$left;
//8.右堆起始
$j=$mid+1;
//9.临时数组起始
$t=0;
//10.左右堆数组都没到末尾
while($i<=$mid && $j<=$right){
//11.左堆小于等于右堆时
if($A[$i]<=$A[$j]){
//12.左堆赋给临时数组,索引加1
$temp[$t++]=$A[$i++];
}else{
//13.右堆赋给临时数组,索引加1
$temp[$t++]=$A[$j++];
}
}
//14.左堆剩余的全部加进临时数组
while($i<=$mid){
$temp[$t++]=$A[$i++];
}
//15.右堆剩余全部加进临时数组
while($j<=$right){
$temp[$t++]=$A[$j++];
}
//16.临时数组的元素重新赋回原数组
for($i=0;$i<$t;$i++){
$A[$left+$i]=$temp[$i];
}
}

//1.利用分治法思想,递归的切分排序元素
function mergeSort(&$A,$temp){
//2.最左只能小于最右,等于的时候就一个元素,大于是不可能的
if($left<$right){
//3.获取中间的元素
$mid=intval(($left+$right)/2);
//4.递归左半区
mergeSort($A,$temp);
//5.递归右半区
mergeSort($A,$mid+1,$temp);
//6.合并两个有序数组为一个有序数组
merge($A,$temp);
}
}

$A=array(2,4,6,1,5,7,3,8,9);
$temp=array();
mergeSort($A,count($A)-1,$temp);
var_dump($A);

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!