PHP教程：詳解PHP歸并排序的實現(xiàn)

　　PHP教程：詳解PHP歸并排序的實現(xiàn)

　　歸并(Merge)排序法是將兩個(或兩個以上)有序表合并成一個新的有序表。歸并排序的一個缺點是它需要存儲器有另一個大小等于數(shù)據(jù)項數(shù)目的數(shù)組。如果初始數(shù)組幾乎占滿整個存儲器，那么歸并排序將不能工作，但是如果有足夠的空間，歸并排序會是一個很好的選擇。

　　假設待排序的序列：

　　4 3 7 9 2 8 6

　　先說思路，歸并排序的中心思想是將兩個已經排序好的序列，合并成一個排序的序列。

　　上面的序列可以分成：

　　4 3 7 9

　　和

　　2 8 6

　　這兩個序列，然后對這兩個序列分別排序：結果為：

　　設置為序列A，與序列B，

　　3 4 7 9

　　2 6 8

　　將上面的兩個序列 合并成一個排序好的序列：

　　合并的具體思路是：

　　設置兩個位置指示器，分別指向序列A與序列B開始的位置：紅色為指示器指向位置：

　　3 4 7 9

　　2 6 8

　　比較兩個指示器所指向的元素的值，將較小的插入到一個新的數(shù)組內，例如序列C，同時將對應的指示器向后移動一位：

　　結果為：

　　3 4 7 9

　　2 6 8

　　形成的序列C：已經被插入一個元素了，剛才較小的 元素2.

　　2

　　然后 再次 比較序列A與序列B中指示器所指向的元素：將小的放入到序列C中，移動相應指針，結果為：

　　3 4 7 9

　　2 6 8

　　2 3

　　以此類推，迭代執(zhí)行，直到序列A或者序列B中某個指示器已經移到到數(shù)組末端。例如：

　　多次比較后，序列B已經將指示器移出到序列末端(最后一個元素之后)了。

　　3 4 7 9

　　2 6 8

　　2 3 4 6 7 8

　　然后將沒有用完的序列，這里面是序列A中其余的元素全部插入到序列C的后邊即可，就剩下一個9 了，將其插入到序列C后即可：

　　序列C結果：

　　2 3 4 5 6 7 8 9

　　這樣就實現(xiàn)了將兩個有序序列合并成一個有序序列的操作，

　　下面先看這個合并的php代碼：

　　/**

　　* 將兩個有序數(shù)組合并成一個有序數(shù)組

　　* @param $arrA,

　　* @param $arrB,

　　* @reutrn array合并好的數(shù)組

　　*/

　　function mergeArray($arrA, $arrB) {

　　$a_i = $b_i = 0;//設置兩個起始位置標記

　　$a_len = count($arrA);

　　$b_len = count($arrB);

　　while($a_i<$a_len && $b_i<$b_len) {

　　//當數(shù)組A和數(shù)組B都沒有越界時

　　if($arrA[$a_i] < $arrB[$b_i]) {

　　$arrC[] = $arrA[$a_i++];

　　} else {

　　$arrC[] = $arrB[$b_i++];

　　}

　　}

　　//判斷 數(shù)組A內的元素是否都用完了，沒有的話將其全部插入到C數(shù)組內：

　　while($a_i < $a_len) {

　　$arrC[] = $arrA[$a_i++];

　　}

　　//判斷 數(shù)組B內的元素是否都用完了，沒有的話將其全部插入到C數(shù)組內：

　　while($b_i < $b_len) {

　　$arrC[] = $arrB[$b_i++];

　　}

　　return $arrC;

　　}

　　經過上面的分析和程序的實現(xiàn)，我們不難發(fā)現(xiàn)，合并已排序的序列的時間應該是線性的，就是說，最多會發(fā)生N-1次比較，其中N是所有元素之和。

　　通過上面的描述，我們實現(xiàn)了將兩個排序好的數(shù)組進行和并的過程。

　　此時，大家可能會有疑問，這個和歸并排序整個序列有什么關系?或者你是如何能夠得到最開始的兩個排序好的子序列的呢?

　　下面，我們就來描述以下什么是歸并排序，然后再看，上面的合并與歸并排序的關系是如何的：

　　大家不妨去想，當我們需要排序如下的數(shù)組時，我們是否可以先將數(shù)組的前半部分與數(shù)組的后半部分分別進行歸并排序，然后將排序的結果合并起來呢?

　　例如：待排序的數(shù)組：

　　4 3 7 9 2 8 6

　　先分成2部分：

　　4 3 7 9

　　2 8 6

　　將前半部分 與 后半部分 分別看成一個序列，再次進行歸并(就是拆分，排序，合并)操作

　　就會變成：

　　前：

　　4 3

　　7 9

　　后：

　　2 8

　　6

　　同樣 再對每個自序列進行 歸并排序，再次(拆分，排序，合并)。

　　當拆分的子序列內只存在一個元素(長度為1)時，那么這個序列就不必再拆分了，就是一個排序好的數(shù)組了。然后將這個序列，與其他的序列再合并到一起即可，最終就將所有的都合并好了，成為一個完整的排序好的數(shù)組。

　　程序實現(xiàn)：

　　通過上面的描述 大家應該想到，可以使用遞歸程序來實現(xiàn)這個程序設計吧：

　　想要實現(xiàn)這個程序，可能需要解決如下問題：

　　怎么將數(shù)組做拆分：

　　設定兩個指示器，一個指向數(shù)組開始假定為$left，一個指向數(shù)組最后一個元素$right：

　　4 3 7 9 2 8 6

　　然 后判斷 $left 是否小于$right，如果小于，說明這個序列內元素個數(shù)大于一個，就將其拆分成兩個數(shù)組，拆分的方式是生成一個中間的指示器$center，值 為$left + $right /2 整除。結果為：3，然后將$left 到$center 分成一組，$center+1到$right分成一組：

　　4 3 7 9

　　2 8 6

　　接下來，遞歸的 利用$left, $center, $center+1, $right分別做為 兩個序列的 左右指示器，進行操作。知道數(shù)組內有一個元素$left==$right .然后按照上面的合并數(shù)組即可：

　　/**

　　* mergeSort 歸并排序

　　* 是開始遞歸函數(shù)的一個驅動函數(shù)

　　* @param &$arr array 待排序的數(shù)組

　　*/

　　function mergeSort(&$arr) {

　　$len = count($arr);//求得數(shù)組長度

　　mSort($arr, 0, $len-1);

　　}

　　/**

　　* 實際實現(xiàn)歸并排序的程序

　　* @param &$arr array 需要排序的數(shù)組

　　* @param $left int 子序列的左下標值

　　* @param $right int 子序列的右下標值

　　*/

　　function mSort(&$arr, $left, $right) {

　　if($left < $right) {

　　//說明子序列內存在多余1個的元素，那么需要拆分，分別排序，合并

　　//計算拆分的位置，長度/2 去整

　　$center = floor(($left+$right) / 2);

　　//遞歸調用對左邊進行再次排序：

　　mSort($arr, $left, $center);

　　//遞歸調用對右邊進行再次排序

　　mSort($arr, $center+1, $right);

　　//合并排序結果

　　mergeArray($arr, $left, $center, $right);

　　}

　　}

　　/**

　　* 將兩個有序數(shù)組合并成一個有序數(shù)組

　　* @param &$arr, 待排序的所有元素

　　* @param $left, 排序子數(shù)組A的開始下標

　　* @param $center, 排序子數(shù)組A與排序子數(shù)組B的中間下標，也就是數(shù)組A的結束下標

　　* @param $right, 排序子數(shù)組B的結束下標(開始為$center+1)

　　*/

　　function mergeArray(&$arr, $left, $center, $right) {

　　//設置兩個起始位置標記

　　$a_i = $left;

　　$b_i = $center+1;

　　while($a_i<=$center && $b_i<=$right) {

　　//當數(shù)組A和數(shù)組B都沒有越界時

　　if($arr[$a_i] < $arr[$b_i]) {

　　$temp[] = $arr[$a_i++];

　　} else {

　　$temp[] = $arr[$b_i++];

　　}

　　}

　　//判斷 數(shù)組A內的元素是否都用完了，沒有的話將其全部插入到C數(shù)組內：

　　while($a_i <= $center) {

　　$temp[] = $arr[$a_i++];

　　}

　　//判斷 數(shù)組B內的元素是否都用完了，沒有的話將其全部插入到C數(shù)組內：

　　while($b_i <= $right) {

　　$temp[] = $arr[$b_i++];

　　}

　　//將$arrC內排序好的部分，寫入到$arr內：

　　for($i=0, $len=count($temp); $i<$len; $i++) {

　　$arr[$left+$i] = $temp[$i];

　　}

　　}

　　//do some test:

　　$arr = array(4, 7, 6, 3, 9, 5, 8);

　　mergeSort($arr);

　　print_r($arr);

　　注意上面的代碼帶排序的數(shù)組都使用的是 引用傳遞，為了節(jié)約空間。

　　而且，其中的合并數(shù)組的方式也為了節(jié)約空間做了相對的修改，把所有的操作都放到了$arr上完成，引用傳遞節(jié)約資源。

　　好了 上面的代碼就完成了歸并排序，歸并排序的時間復雜度為O(N*LogN) 效率還是相當客觀的。

　　再說，歸并排序算法，中心思想是 將一個復雜問題分解成相似的小問題，再把小問題分解成更小的問題，直到分解到可以馬上求解為止，然后將分解得到的結果再合并起來的一種方法。這個思想用個 成語形容叫化整為零。 放到計算機科學中有個專業(yè)屬于叫分治策略(分治發(fā))。分就是大問題變小問題，治就是小結果合并成大結果。

　　分治策略是很多搞笑算法的基礎，我們在討論快速排序時，也會用到分治策略的。

　　最后簡單的說一下這個算法，雖然這個算法在時間復雜度上達到了O(NLogN)。但是還是會有一個小問題，就是在合并兩個數(shù)組時，如果數(shù)組的總元素個數(shù)為 N，那么我們需要再開辟一個同樣大小的空間來保存合并時的數(shù)據(jù)(就是mergeArray中的$temp數(shù)組)，而且還需要將數(shù)據(jù)有$temp拷貝 會$arr，因此會浪費一些資源。因此在實際的排序中還是 相對的較少使用。