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

為企業(yè)提供成都做網(wǎng)站、網(wǎng)站設(shè)計(jì)、網(wǎng)站優(yōu)化、營(yíng)銷型網(wǎng)站建設(shè)、競(jìng)價(jià)托管、品牌運(yùn)營(yíng)等營(yíng)銷獲客服務(wù)。創(chuàng)新互聯(lián)擁有網(wǎng)絡(luò)營(yíng)銷運(yùn)營(yíng)團(tuán)隊(duì)，以豐富的互聯(lián)網(wǎng)營(yíng)銷經(jīng)驗(yàn)助力企業(yè)精準(zhǔn)獲客，真正落地解決中小企業(yè)營(yíng)銷獲客難題，做到“讓獲客更簡(jiǎn)單”。自創(chuàng)立至今，成功用技術(shù)實(shí)力解決了企業(yè)“網(wǎng)站建設(shè)、網(wǎng)絡(luò)品牌塑造、網(wǎng)絡(luò)營(yíng)銷”三大難題，同時(shí)降低了營(yíng)銷成本，提高了有效客戶轉(zhuǎn)化率，獲得了眾多企業(yè)客戶的高度認(rèn)可！

歸并(Merge)排序法是將兩個(gè)(或兩個(gè)以上)有序表合并成一個(gè)新的有序表。歸并排序的一個(gè)缺點(diǎn)是它需要存儲(chǔ)器有另一個(gè)大小等于數(shù)據(jù)項(xiàng)數(shù)目的數(shù)組。如果初始數(shù)組幾乎占滿整個(gè)存儲(chǔ)器，那么歸并排序?qū)⒉荒芄ぷ?，但是如果有足夠的空間，歸并排序會(huì)是一個(gè)很好的選擇。

假設(shè)待排序的序列：

4 3 7 9 2 8 6

先說(shuō)思路，歸并排序的中心思想是將兩個(gè)已經(jīng)排序好的序列，合并成一個(gè)排序的序列。

上面的序列可以分成：

4 3 7 9

和

2 8 6

這兩個(gè)序列，然后對(duì)這兩個(gè)序列分別排序：結(jié)果為：

設(shè)置為序列A，與序列B，

3 4 7 9

2 6 8

將上面的兩個(gè)序列 合并成一個(gè)排序好的序列：

合并的具體思路是：

設(shè)置兩個(gè)位置指示器，分別指向序列A與序列B開(kāi)始的位置：紅色為指示器指向位置：

3 4 7 9

2 6 8

比較兩個(gè)指示器所指向的元素的值，將較小的插入到一個(gè)新的數(shù)組內(nèi)，例如序列C，同時(shí)將對(duì)應(yīng)的指示器向后移動(dòng)一位：

結(jié)果為：

3 4 7 9

2 6 8

形成的序列C：已經(jīng)被插入一個(gè)元素了，剛才較小的 元素2.

2

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

3 4 7 9

2 6 8

2 3

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

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

3 4 7 9

2 6 8

2 3 4 6 7 8

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

序列C結(jié)果：

2 3 4 5 6 7 8 9

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

下面先看這個(gè)合并的php代碼：

/**

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

* @param $arrA,

* @param $arrB,

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

*/

function mergeArray($arrA, $arrB) {

$a_i = $b_i = 0;//設(shè)置兩個(gè)起始位置標(biāo)記

$a_len = count($arrA);

$b_len = count($arrB);

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

//當(dāng)數(shù)組A和數(shù)組B都沒(méi)有越界時(shí)

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

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

} else {

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

}

}

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

while($a_i < $a_len) {

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

}

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

while($b_i < $b_len) {

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

}

return $arrC;

}

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

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

此時(shí)，大家可能會(huì)有疑問(wèn)，這個(gè)和歸并排序整個(gè)序列有什么關(guān)系?或者你是如何能夠得到最開(kāi)始的兩個(gè)排序好的子序列的呢?

下面，我們就來(lái)描述以下什么是歸并排序，然后再看，上面的合并與歸并排序的關(guān)系是如何的：

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

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

4 3 7 9 2 8 6

先分成2部分：

4 3 7 9

2 8 6

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

就會(huì)變成：

前：

4 3

7 9

后：

2 8

6

同樣 再對(duì)每個(gè)自序列進(jìn)行 歸并排序，再次(拆分，排序，合并)。

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

程序?qū)崿F(xiàn)：

通過(guò)上面的描述 大家應(yīng)該想到，可以使用遞歸程序來(lái)實(shí)現(xiàn)這個(gè)程序設(shè)計(jì)吧：

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

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

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

4 3 7 9 2 8 6

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

4 3 7 9

2 8 6

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

/**

* mergeSort 歸并排序

* 是開(kāi)始遞歸函數(shù)的一個(gè)驅(qū)動(dòng)函數(shù)

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

*/

function mergeSort(&$arr) {

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

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

}

/**

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

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

* @param $left int 子序列的左下標(biāo)值

* @param $right int 子序列的右下標(biāo)值

*/

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

if($left < $right) {

//說(shuō)明子序列內(nèi)存在多余1個(gè)的元素，那么需要拆分，分別排序，合并

//計(jì)算拆分的位置，長(zhǎng)度/2 去整

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

//遞歸調(diào)用對(duì)左邊進(jìn)行再次排序：

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

//遞歸調(diào)用對(duì)右邊進(jìn)行再次排序

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

//合并排序結(jié)果

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

}

}

/**

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

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

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

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

* @param $right, 排序子數(shù)組B的結(jié)束下標(biāo)(開(kāi)始為$center+1)

*/

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

//設(shè)置兩個(gè)起始位置標(biāo)記

$a_i = $left;

$b_i = $center+1;

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

//當(dāng)數(shù)組A和數(shù)組B都沒(méi)有越界時(shí)

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

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

} else {

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

}

}

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

while($a_i <= $center) {

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

}

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

while($b_i <= $right) {

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

}

//將$arrC內(nèi)排序好的部分，寫入到$arr內(nèi)：

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é)約空間做了相對(duì)的修改，把所有的操作都放到了$arr上完成，引用傳遞節(jié)約資源。

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

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

分治策略是很多搞笑算法的基礎(chǔ)，我們?cè)谟懻摽焖倥判驎r(shí)，也會(huì)用到分治策略的。

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

本文標(biāo)題：PHP教程：詳解PHP歸并排序的實(shí)現(xiàn)
標(biāo)題來(lái)源：http://chinadenli.net/article34/giojpe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供企業(yè)建站、域名注冊(cè)、商城網(wǎng)站、、App設(shè)計(jì)、品牌網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)