/**
* 不断地从中间切分
* 归并排序，可以保证在合并前后相同值得元素的先后顺序不变
* 时间复杂度为O(nlogn）
* 时间复杂度是稳定的
* 空间复杂度为O(N)
* @param $arr
* @param $n
* @return array
*/
function merge_sort($arr, $n)
{
return merge_sort_c($arr, 0, $n-1);
}
function merge_sort_c($arr, $l, $r)
{
if ($l >= $r) {
return [$arr[$r]];
}
$p = (int)(($l+$r)/2);
$left = merge_sort_c($arr, $l, $p);
$right = merge_sort_c($arr, $p+1, $r);
$merger = merger($left, $right);
return $merger;
}
function merger($l, $r)
{
$tmp = [];
$lengthLeft = count($l);
$lengthRight = count($r);
$i=$j=0;
do {
if ($l[$i] > $r[$j]) {
$tmp[] = $r[$j++];
} else {
$tmp[] = $l[$i++];
}
} while($i<$lengthLeft && $j<$lengthRight);
if ($i < $lengthLeft) {
$start = $i;
do{
$tmp[] = $l[$start++];
} while ($start < $lengthLeft);
}
if ($j < $lengthRight) {
$start = $j;
do{
$tmp[] = $r[$start++];
} while ($start < $lengthRight);
}
return $tmp;
}
/**
* 快速排序
* 需要寻找分区点，将数组切分成三部分，小于分区点，分区点，大于分区点
* 原地不稳定
* 时间复杂度O（nlogn) 极端情况下，复杂度会变成O(n^2）
*
*
*/
function quick_sort(&$arr)
{
$n = count($arr);
if ($n <= 1) {
return;
}
quick_fort_c($arr, 0, $n-1);
}
function quick_fort_c(&$arr, $p, $r)
{
if ($p >= $r) {
return;
}
$m = partition($arr, $p, $r);
quick_fort_c($arr, $p, $m-1);
quick_fort_c($arr, $m+1, $r);
}
function partition(&$arr, $p, $r)
{
$privot = $arr[$r];
$i = $p;
for ($j=$p; $j<$r-1;$j++) {
if ($arr[$j] < $privot) {
$tmp = $arr[$j];
$arr[$j] = $arr[$i];
$arr[$i] = $tmp;
}
$i++;
}
$tmp = $arr[$r];
$arr[$r] = $arr[$i];
$arr[$i] = $tmp;
return $i;
}
