歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。 ``` //merge函數將指定的兩個有序數組(arr1,arr2)合并并且排序 //我們可以找到第三個數組,然后依次從兩個數組的開始取數據哪個數據小就先取哪個的,然后刪除掉剛剛取過///的數據 function al_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); } //歸并排序主程序 function al_merge_sort($arr){ $len = count($arr); if($len <= 1) return $arr;//遞歸結束條件,到達這步的時候,數組就只剩下一個元素了,也就是分離了數組 $mid = intval($len/2);//取數組中間 $left_arr = array_slice($arr, 0, $mid);//拆分數組0-mid這部分給左邊left_arr $right_arr = array_slice($arr, $mid);//拆分數組mid-末尾這部分給右邊right_arr $left_arr = al_merge_sort($left_arr);//左邊拆分完后開始遞歸合并往上走 $right_arr = al_merge_sort($right_arr);//右邊拆分完畢開始遞歸往上走 $arr = al_merge($left_arr, $right_arr);//合并兩個數組,繼續遞歸 return $arr; } $arr = array(12, 5, 4, 7, 8, 3, 4, 2, 6, 4, 9); print_r(al_merge_sort($arr)); ```