基本思想
歸並排序的主要思想是分治法。
主要過程是：
1.將n個元素從中間切開，分成兩部分。（左邊可能比右邊多1個數）
2.將步驟1分成的兩部分，再分別進行遞歸分解。直到所有部分的元素個數都爲1。
3.從最底層開始逐步合並兩個排好序的數列。
完整過程
首先我們看到，一個無序的數組如下，爲了簡約，以及簡便解釋，我們定義了8個元素。
然後，我們把該8個元素進行劃分，分成左邊四個，和右邊四個
依次按照上邊的方法，把剩餘的數組繼續拆分，一直拆到只剩下一個元素的時候，停止
由於存在8個單獨的子元素，然後我們兩兩把元素合並，並且按照一定順序排序
此時，我們可以看到我們又得到了四個不同顔色的數組，並且在這個數組裡邊，也是按照一定的順序排好序的。隨後，繼續利用這種方法，把剩餘的繼續合並，一直合並到所有數都在一個數組裡邊。此時便是完成了合並。
整個過程(包括拆分和合並)如下：
代碼如下:
// 歸並排序主程序function mergeSort($arr) {
$len = count($arr);
if ($len <= 1) {
return $arr;
}
// 遞歸結束條件, 到達這步的時候, 數組就只剩下一個元素了, 也就是分離了數組
$mid = intval($len / 2); // 取數組中間
$left = array_slice($arr, 0, $mid); // 拆分數組0-mid這部分給左邊left
$right = array_slice($arr, $mid); // 拆分數組mid-末尾這部分給右邊right
$left = mergeSort($left); // 左邊拆分完後開始遞歸合並往上走
$right = mergeSort($right); // 右邊拆分完畢開始遞歸往上走
$arr = merge($left, $right); // 合並兩個數組,繼續遞歸
return $arr;
}
// merge函數將指定的兩個有序數組(arrA, arr)合並並且排序function merge($arrA, $arrB) {
$arrC = array();
while (count($arrA) && count($arrB)) {
// 這裡不斷的判斷哪個值小, 就將小的值給到arrC, 但是到最後肯定要剩下幾個值,
// 不是剩下arrA裡面的就是剩下arrB裡面的而且這幾個有序的值, 肯定比arrC裡面所有的值都大所以使用
$arrC[] = $arrA[0] < $arrB[0] ? array_shift($arrA) : array_shift($arrB);
}
return array_merge($arrC, $arrA, $arrB);
}結果如下:
$startTime = microtime(1);
$arr = range(1, 10);
shuffle($arr);
echo "before sort: ", implode(', ', $arr), "\n";
$sortArr = mergeSort($arr);
echo "after sort: ", implode(', ', $sortArr), "\n";
echo "use time: ", microtime(1) - $startTime, "s\n";
