PHP实现-归并排序
2018-03-20 15:34 By
"Powerless"
3455
0
1
思路分析
利用归并（合并）的思想实现的排序方法。它的原理是假设初始序列含有 n 个元素，则可以看成是 n 个有序的子序列，每个子序列的长度为 1，然后两两归并，得到 ⌈ n / 2⌉ （⌈ x ⌉ 表示不小于 x 的最小整数）个长度为 2 或 1 的有序序列；再两两归并，······，如此重复，直至得到一个长度为 n 的有序序列为止，这种排序方法就成为 2 路归并排序。
//归并算法总函数
function MergeSort(array &$arr){
$start = 0;
$end = count($arr) - 1;
MSort($arr,$start,$end);
}
function MSort(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]
}
}
//归并操作
function Merge(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; $i<=$end; $i++){
$arr[$i] = $temparr[$i];
}
}
$arr = array(9,1,5,8,3,7,4,6,2);
MergeSort($arr);
var_dump($arr);
小结：
时间复杂度：O(n log n)
空间复杂度：O(n)
归并算法无论原来的序列是否有序都会进行分组和比较
归并排序属于稳定排序
View in WeChat
Others Discussion
-
MySQL分组 Posted on 2019-11-18 14:00
-
PHP7不兼容性 Posted on 2018-03-07 15:59
-
一些常见的基础概念 Posted on 2018-11-28 19:10
-
HTTP头中隐藏PHP版本号 Posted on 2021-01-11 16:38
-
QPS、TPS、RT、吞吐量到底是什么 Posted on 2020-02-02 01:15
-
MySQL事务介绍 Posted on 2019-06-05 18:14
-
能创建多少个 TCP 连接？ Posted on 2021-08-02 16:00
-
MySQL中的行级锁,表级锁,页级锁 Posted on 2018-08-25 11:00
评 论