[PHP]算法-归并排序的PHP实现php 排序
<?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,$left,$right,$temp){
//2.最左只能小于最右,等于的时候就一个元素,大于是不可能的
if($left<$right){
//3.获取中间的元素
$mid=intval(($left+$right)/2);
//4.递归左半区
mergeSort($A,$left,$mid,$temp);
//5.递归右半区
mergeSort($A,$mid+1,$right,$temp);
//6.合并两个有序数组为一个有序数组
merge($A,$left,$mid,$right,$temp);
}
}
$A=array(2,4,6,1,5,7,3,8,9);
$temp=array();
mergeSort($A,0,count($A)-1,$temp);
var_dump($A);