<?php

/**

  • 并归排序

  • 思想:将数据排序,一个小的,一个大的,这样遍历数据得时候,这样第一次遍历得时候可以得到一个(小,大),(小,大)数组

  • 然后通过递归合并,(小1,大1),(小2,大2)每次取出2个数组的第一个数,比较,哪个小,放到一个新的数据tmp里面,然后小的数组current指针后移,继续比较,如果大1<小2,将大1放到

  • tmp里面,然后将剩余的小2,大2依次放入数组,就是两个数组合并排序完了,即tmp = array(小1,大1,小2,大2)

  • 如果刚才大1>小2,则先放入小2,然后(小2,大2)的数组current后移,然后比较大1和大2,如果大1>大2,则大2先放入tmp数组,剩下的大1,放入数组,就是(小1,小2,大2,大1)升序的排好数组

*/

//测试类

class MergeTest

{

private $data;

public function __construct($data)

{

$this->init($data);

}

//执行

public function run()

{

$this->merge();

print_r($this->data);

}

//初始化并归数组,相邻两个元素合并为一个数组(小的在前面)

private function init($data)

{

$tmp = [];

$num = count($data);

if ($num % 2 == 0) {

$items = $num / 2;

} else {

$items = ($num – 1) / 2;

}

for ($i = 0; $i < $items; $i++) {

if ($data[2 * $i] < $data[2 * $i + 1]) {

array_push($tmp, [$data[2 * $i], $data[2 * $i + 1]]);

} else {

array_push($tmp, [$data[2 * $i + 1], $data[2 * $i]]);

}

}

if ($num % 2 != 0) {

array_push($tmp, [$data[$num – 1]]);

}

$this->data = $tmp;

}

//并归递归调用

private function merge()

{

$re = [];

$size = count($this->data);

if ($size != 1) //没有完成并归,继续

{

for ($i = 0; $i < $size – 1; $i += 2) {

$re[] = $this->doubleMerge($this->data[$i], $this->data[$i + 1]);

}

if ($size % 2 != 0) {

$re[] = $this->data[$size – 1];

}

$this->data = $re;

$this->merge();

}

}

//合并两个有序序列

private function doubleMerge($a, $b)

{

$re = [];

$i = $j = 0;

$s1 = count($a);

$s2 = count($b);

while (true) {

if ($a[$i] <= $b[$j]) {

array_push($re, $a[$i]);

$i++;

} else {

array_push($re, $b[$j]);

$j++;

}

if ($i == $s1) {

return array_merge($re, array_slice($b, $j));

}

if ($j == $s2) {

return array_merge($re, array_slice($a, $i));

}

}

}

}

$a = new MergeTest([3,8,8,19, 1, 9, 2, 7, 6, 11,19, 5, 4, 13]);

$a->run();