风火家人开发记要

算法之 分治法/递归排序/归并排序 代码PHP版

• 2017年03月14日
• by chenxue4076
• 8 years ago

先定义递归/分治/归并函数 function merge_sort($data = array(), $start = 0, $length = 0) { if($length – $start > 1) { $middle = floor(($start + $length) / 2); $data = merge_sort($data, $start, $middle); $data = merge_sort($data, $middle, $length); $data = merge($data, $start, $middle, $length); } return $data; } function merge($data = array(), $start=0, $middle=0, $length=0) { $left = $middle – $start; $right = $length – $middle; $array_left = array(); $array_right = array(); for($i = 0; $i < $left; $i++) { $array_left[$i] = $data[$start + $i]; } for($j = 0; $j < $right; $j++) { $array_right[$j] = $data[$middle + $j]; } $m = $n = 0; for($k = $start; $k < $length; $k++) { if( ! empty($array_left[$m]) && ! empty($array_right[$n])) { if($array_left[$m] <= $array_right[$n]) { $data[$k] = $array_left[$m]; $m++; } else { $data[$k] = $array_right[$n]; $n++; } } elseif ( ! empty($array_left[$m])) { $data[$k] = $array_left[$m]; $m++; } else { $data[$k] = $array_right[$n]; $n++; } } return $data; } 调用方法 $result = merge_sort($data, 0, count($data)) 返回一个升序的数组 时间复杂度 Θ(n lgn) 难点： 感觉到处是难点  虽然自己成功调试出正确结果，但总是感觉不能全部理解。 (353)