php怎麼實現並歸排序
2022-10-21 10:00:32
php實現並歸排序的方法：1、建立一個PHP範例檔案；2、定義「public function handle(){...}」方法；3、通過「private function mergeSort($a, $lo, $hi) {...}」方法把資料逐步分解；4、通過「merge」方法對分解後的資料進行排序，再合併到一起即可。
php入門到就業線上直播課：進入學習
Apipost = Postman + Swagger + Mock + Jmeter 超好用的API偵錯工具：
php實現歸併排序演演算法
歸併排序演演算法的複雜度是O(nlogn)。
程式碼如下,只需要clone下來執行composer install然後執行 php artisan test:mergeSort 就可以看到結果了
/**
* 歸併排序把資料逐步分解，然後對分解後的資料進行排序，最後合併到一起
*
* @return mixed
*/
public function handle()
{
$this->a = [3,70,4,38,5,6,8,4,7,10,6,10,34,4];
dump($this->a);
$a = $this->mergeSort($this->a, 0, count($this->a));
dd($a);
}
private function mergeSort($a, $lo, $hi) {
if (($hi - $lo) < 2) return [$a[$lo]];
$mi = ($lo + $hi) >> 1;
//把中點左邊的進行歸併
$b = $this->mergeSort($a, $lo, $mi);
dump('$b:',$b);
//把中點右邊的進行歸併
$c = $this->mergeSort($a, $mi, $hi);
dump('$c:',$c);
//把所有資料進行排序
return $this->merge($b, $c, $lo,$mi,$hi);
}
/**
* 假設有一個陣列$a分成了兩個陣列[3,4] [2,8]
* 逐一比較，3and2，取出來2然後3and8取出來3然後4and8取出來4，最後取出來8
*
* @param [type] $lo
* @param [type] $mi
* @param [type] $hi
* @return void
*/
private function merge($b, $c, $lo, $mi, $hi) {
$lb = $mi - $lo; //$b陣列的邊界
$lc = $hi - $mi; //$c陣列的邊界
$res = [];
//$i表示合併後陣列的下標 $ib是b陣列的下標 $ic是c陣列的下標
for($i = 0,$ib=0,$ic=0;$ib<$lb || $ic < $lc;){
//ib 下標沒有越界 && c的陣列已經空了也就是$ic >= $lc || 比較兩個陣列首位的大小 如果b的首元素 < c的首元素，那麼取出來b的首元素
if ($ib < $lb && ( $ic >= $lc || $b[$ib] <= $c[$ic])) {
$res[$i++] = $b[$ib++];
}
//k 下標沒有越界 && b的陣列已經空了也就是$ib >= $lb || 如果c的首元素 < b的首元素，那麼取出來c的首元素
if ($ic < $lc && ($ib >= $lb || $b[$ib] > $c[$ic])) {
$res[$i++] = $c[$ic++];
}
}
return $res;
}登入後複製歸併排序原理
歸併排序和快排剛好相反，是先將整個陣列左右打散，然後在逐一合併進行排序，最終完成整個陣列的排序，排序示意圖如下：
首先將整個陣列左右打散，變成單個元素，因為單個元素可以被認為是有序的。
對應程式碼
if (($hi - $lo) < 2) return [$a[$lo]];
$mi = ($lo + $hi) >> 1;
//把中點左邊的進行歸併
$b = $this->mergeSort($a, $lo, $mi);
dump('$b:',$b);
//把中點右邊的進行歸併
$c = $this->mergeSort($a, $mi, $hi);
dump('$c:',$c);登入後複製接下來對左右兩個有序陣列進行排序，假設有一個陣列$a分成了兩個陣列[3,4] [2,8]，逐一比較，3and2，取出來2然後3and8取出來3然後4and8取出來4，最後取出來8，對應程式碼：
$lb = $mi - $lo; //$b陣列的邊界
$lc = $hi - $mi; //$c陣列的邊界
$res = [];
//$i表示合併後陣列的下標 $ib是b陣列的下標 $ic是c陣列的下標
for($i = 0,$ib=0,$ic=0;$ib<$lb || $ic < $lc;){
//ib 下標沒有越界 && c的陣列已經空了也就是$ic >= $lc || 比較兩個陣列首位的大小 如果b的首元素 < c的首元素，那麼取出來b的首元素
if ($ib < $lb && ( $ic >= $lc || $b[$ib] <= $c[$ic])) {
$res[$i++] = $b[$ib++];
}
//k 下標沒有越界 && b的陣列已經空了也就是$ib >= $lb || 如果c的首元素 < b的首元素，那麼取出來c的首元素
if ($ic < $lc && ($ib >= $lb || $b[$ib] > $c[$ic])) {
$res[$i++] = $c[$ic++];
}
}
return $res;登入後複製示意圖如下：
推薦學習：《》
以上就是php怎麼實現並歸排序的詳細內容，更多請關注TW511.COM其它相關文章！
