# 歸并排序 ## 定義： > 指的是如果要排序一個數組，我們先把數組從中間分成前后兩部分，然后對前后兩部分分別排序，再將排好序的兩部分合并在一起，這樣整個數組就都有序了。歸并排序使用了分治思想，分治，顧名思義，就是分而治之，將一個大問題分解成小的子問題來解決。說到這里，可能你就能聯想起我們之前講到的一個編程技巧 —— 遞歸，沒錯，歸并排序就是通過遞歸來實現的。這個遞歸的公式是每次都將傳入的待排序數組一分為二，直到不能分割，然后將排序后序列合并，最終返回排序后的數組。原理圖如下所示：  ## 代碼: ~~~ * 歸并排序 * @param $nums * @return mixed * 4 5 6 3 2 1 */ function merge_sort($nums) { if (count($nums) <= 1) { return $nums; } merge_sort_c($nums, 0, count($nums) - 1); return $nums; } function merge_sort_c(&$nums, $p, $r)//傳入待排序數組,$p和$r分別為起始和結束下標 { if ($p >= $r) {//不能分割 return; } $q = floor(($p + $r) / 2); merge_sort_c($nums, $p, $q);//分割后左邊部分 merge_sort_c($nums, $q + 1, $r);//分割后右邊部分 merge($nums, ['start' => $p, 'end' => $q], ['start' => $q + 1, 'end' => $r]);//排序并合并數組 } function merge(&$nums, $nums_p, $nums_q) { $temp = []; $i = $nums_p['start']; $j = $nums_q['start']; $k = 0; while ($i <= $nums_p['end'] && $j <= $nums_q['end']) { if ($nums[$i] <= $nums[$j]) { $temp[$k++] = $nums[$i++]; } else { $temp[$k++] = $nums[$j++]; } } if ($i <= $nums_p['end']) { for (; $i <= $nums_p['end']; $i++) { $temp[$k++] = $nums[$i]; } } if ($j <= $nums_q['end']) { for (; $j <= $nums_q['end']; $j++) { $temp[$k++] = $nums[$j]; } } for ($x = 0; $x < $k; $x++) { $nums[$nums_p['start'] + $x] = $temp[$x]; } } $nums = [4, 5, 6, 3, 2, 1]; $nums = merge_sort($nums); print_r($nums); ~~~