forked from m9rco/algorithm-php
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMergeSort.php
More file actions
97 lines (89 loc) · 3.44 KB
/
MergeSort.php
File metadata and controls
97 lines (89 loc) · 3.44 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
<?php
/**
* @example 归并排序
* @author ShaoWei Pu <[email protected]>
* @date 2017/7/22
* @license Mozilla
* -------------------------------------------------------------
* 思路分析：
* -------------------------------------------------------------
* 比较a[i]和b[j]的大小，若a[i]≤b[j]，则将第一个有序表中的元素a[i]复制到r[k]中，
* 并令i和k分别加上1；否则将第二个有序表中的元素b[j]复制到r[k]中，并令j和k分别加上1，
* 如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。
* 归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，
* 最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]
*/
class MergeSort
{
/**
* MergeSort constructor.
* 是开始递归函数的一个驱动函数
*
* @param array $arr 待排序的数组
*/
public function __construct(array $arr)
{
$this->mSort($arr, 0, count($arr) - 1);
var_dump($arr);
}
/**
* 实际实现归并排序的程序
*
* @param $arr array 需要排序的数组
* @param $left int 子序列的左下标值
* @param $right int 子序列的右下标值
*/
public function mSort(&$arr, $left, $right)
{
if ($left < $right) {
//说明子序列内存在多余1个的元素，那么需要拆分，分别排序，合并
//计算拆分的位置，长度/2 去整
$center = floor(($left + $right) / 2);
//递归调用对左边进行再次排序：
$this->mSort($arr, $left, $center);
//递归调用对右边进行再次排序
$this->mSort($arr, $center + 1, $right);
//合并排序结果
$this->mergeArray($arr, $left, $center, $right);
}
}
// 4, 7, 6, 3, 9, 5, 8
//
/**
* 将两个有序数组合并成一个有序数组
*
* @param &$arr , 待排序的所有元素
* @param $left , 排序子数组A的开始下标
* @param $center , 排序子数组A与排序子数组B的中间下标，也就是数组A的结束下标
* @param $right , 排序子数组B的结束下标（开始为$center+1)
*/
public function mergeArray(&$arr, $left, $center, $right)
{
//设置两个起始位置标记
$a_i = $left;
$b_i = $center + 1;
$temp = [];
while ($a_i <= $center && $b_i <= $right){
//当数组A和数组B都没有越界时
if ($arr[ $a_i ] < $arr[ $b_i ]) {
$temp[] = $arr[ $a_i++ ];
} else {
$temp[] = $arr[ $b_i++ ];
}
}
//判断 数组A内的元素是否都用完了，没有的话将其全部插入到C数组内：
while ($a_i <= $center){
$temp[] = $arr[ $a_i++ ];
}
//判断 数组B内的元素是否都用完了，没有的话将其全部插入到C数组内：
while ($b_i <= $right){
$temp[] = $arr[ $b_i++ ];
}
//将$arrC内排序好的部分，写入到$arr内：
for ($i = 0, $len = count($temp); $i < $len; $i++){
$arr[ $left + $i ] = $temp[ $i ];
}
}
}
//do some test:
new mergeSort([4, 7, 6, 3, 9, 5, 8]);