[PHP]算法-归并排序的PHP实现
程序员文章站
2022-05-04 14:08:46
<?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);
上一篇: C++ 学习笔记 (六) 继承- 子类与父类有同名函数,变量
下一篇: python读写音频文件小结