首頁 後端開發 php教程 PHP實作歸併排序的方法

PHP實作歸併排序的方法

May 31, 2018 pm 03:09 PM
php 排序 方法

本文主要介紹了php歸併排序的實作演算法,也就是把待排序序列分成若干個有序的子序列,再把有序的子序列合併為整體有序序列。有興趣的朋友可以來了解一下。

歸併(Merge)排序法是將兩個(或兩個以上)有序表合併成一個新的有序表。歸併排序的一個缺點是它需要記憶體有另一個大小等於資料項數目的陣列。如果初始陣列幾乎佔滿整個記憶體,那麼歸併排序將無法運作,但是如果有足夠的空間,歸併排序會是一個很好的選擇。

假設待排序的序列:

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
比較兩個指標所指向的元素的值,將較小的插入到一個新的陣列內,例如序列C,同時將對應的指示器向後移動一位:

結果為:



3

4 7 96
  8
形成的序列C:已經被插入一個元素了,剛才較小的元素2.

2



#然後再次比較序列A與序列B中指示器所指向的元素:將小的放入到序列C中,移動對應指針,結果為:


3

4

7 9
# 82  3

以此類推,迭代執行,直到序列A或序列B中某個指示器已經移到陣列末端。例如:

多次比較後,序列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

這樣就實現了將兩個有序序列合併成一個有序序列的操作,

下面先看這個合併的php程式碼:


/**
 * 将两个有序数组合并成一个有序数组
 * @param $arrA,
 * @param $arrB,
 * @reutrn array合并好的数组
 */
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) {
    //当数组A和数组B都没有越界时
    if($arrA[$a_i] < $arrB[$b_i]) {
      $arrC[] = $arrA[$a_i++];
    } else {
      $arrC[] = $arrB[$b_i++];
    }
  }
  //判断 数组A内的元素是否都用完了,没有的话将其全部插入到C数组内:
  while($a_i < $a_len) {
    $arrC[] = $arrA[$a_i++];
  }
  //判断 数组B内的元素是否都用完了,没有的话将其全部插入到C数组内:
  while($b_i < $b_len) {
    $arrC[] = $arrB[$b_i++];
  }
  return $arrC;
}
登入後複製


經過上面的分析和程式的實現,我們不難發現,合併已排序的序列的時間應該是線性的,就是說,最多會發生N-1次比較,其中N是所有元素總和。

透過上面的描述,我們實作了將兩個排序好的陣列進行和併的過程。

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

下面,我們就來描述以下什麼是歸併排序,然後再看,上面的合併與歸併排序的關係是如何的:


大家不妨去想,當我們需要排序如下的數組時,我們是否可以先將陣列的前半部與陣列的後半部分別進行歸併排序,然後將排序的結果合併呢?


例如:待排序的陣列:
4 3 7 9 2 8 6


先分成2部分:

##4 3 7 9

2 8 6


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

就會變成:



前:
4 3

7 9

#後:

2 8

  6
#同樣  再對每個自序列進行歸併排序,再次(拆分,排序,合併)。

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

程式實作:


透過上面的描述大家應該想到,可以用遞迴程式來實現這個程式設計:


想要實作這個程序,可能需要解決如下問題:怎麼將陣列做拆分:

設定兩個指示器,指向數組開始假設為$left,一個指向陣列最後一個元素$right:######4### 3 7 9 2 8 ###6#########

然 后判断 $left 是否小于$right,如果小于,说明这个序列内元素个数大于一个,就将其拆分成两个数组,拆分的方式是生成一个中间的指示器$center,值 为$left + $right /2 整除。结果为:3,然后将$left 到$center 分成一组,$center+1到$right分成一组:
4 3 7 9
2 8 6
接下来,递归的 利用$left, $center, $center+1, $right分别做为 两个序列的 左右指示器,进行操作。知道数组内有一个元素$left==$right .然后按照上面的合并数组即可:

/**
* mergeSort 归并排序
* 是开始递归函数的一个驱动函数
* @param &$arr array 待排序的数组
*/
function mergeSort(&$arr) {
  $len = count($arr);//求得数组长度
 
  mSort($arr, 0, $len-1);
}
/**
* 实际实现归并排序的程序
* @param &$arr array 需要排序的数组
* @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);
  }
}
 
/**
* 将两个有序数组合并成一个有序数组
* @param &$arr, 待排序的所有元素
* @param $left, 排序子数组A的开始下标
* @param $center, 排序子数组A与排序子数组B的中间下标,也就是数组A的结束下标
* @param $right, 排序子数组B的结束下标(开始为$center+1)
*/
function mergeArray(&$arr, $left, $center, $right) {
  //设置两个起始位置标记
  $a_i = $left;
  $b_i = $center+1;
  while($a_i<=$center && $b_i<=$right) {
    //当数组A和数组B都没有越界时
    if($arr[$a_i] < $arr[$b_i]) {
      $temp[] = $arr[$a_i++];
    } else {
      $temp[] = $arr[$b_i++];
    }
  }
  //判断 数组A内的元素是否都用完了,没有的话将其全部插入到C数组内:
  while($a_i <= $center) {
    $temp[] = $arr[$a_i++];
  }
  //判断 数组B内的元素是否都用完了,没有的话将其全部插入到C数组内:
  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);
登入後複製

注意上面的代码带排序的数组都使用的是 引用传递,为了节约空间。

而且,其中的合并数组的方式也为了节约空间做了相对的修改,把所有的操作都放到了$arr上完成,引用传递节约资源。

好了 上面的代码就完成了归并排序,归并排序的时间复杂度为O(N*LogN) 效率还是相当客观的。

再说,归并排序算法,中心思想是 将一个复杂问题分解成相似的小问题,再把小问题分解成更小的问题,直到分解到可以马上求解为止,然后将分解得到的结果再合并起来的一种方法。这个思想用个 成语形容叫化整为零。 放到计算机科学中有个专业属于叫分治策略(分治发)。分就是大问题变小问题,治就是小结果合并成大结果。

分治策略是很多搞笑算法的基础,我们在讨论快速排序时,也会用到分治策略的。

最后简单的说一下这个算法,虽然这个算法在时间复杂度上达到了O(NLogN)。但是还是会有一个小问题,就是在合并两个数组时,如果数组的总元素个数为 N,那么我们需要再开辟一个同样大小的空间来保存合并时的数据(就是mergeArray中的$temp数组),而且还需要将数据有$temp拷贝 会$arr,因此会浪费一些资源。因此在实际的排序中还是 相对的较少使用。

总结:以上就是本篇文的全部内容,希望能对大家的学习有所帮助。

相关推荐:

PHP使用curl_multi实现并发请求的方法示例

PHP性能测试工具xhprof安装与使用方法详解

PHP实现通过strace定位故障原因的方法

以上是PHP實作歸併排序的方法的詳細內容。更多資訊請關注PHP中文網其他相關文章!

本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱門文章

<🎜>:泡泡膠模擬器無窮大 - 如何獲取和使用皇家鑰匙
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
北端:融合系統,解釋
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
Mandragora:巫婆樹的耳語 - 如何解鎖抓鉤
3 週前 By 尊渡假赌尊渡假赌尊渡假赌

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

熱門話題

Java教學
1664
14
CakePHP 教程
1423
52
Laravel 教程
1321
25
PHP教程
1269
29
C# 教程
1249
24
PHP和Python:比較兩種流行的編程語言 PHP和Python:比較兩種流行的編程語言 Apr 14, 2025 am 12:13 AM

PHP和Python各有優勢,選擇依據項目需求。 1.PHP適合web開發,尤其快速開發和維護網站。 2.Python適用於數據科學、機器學習和人工智能,語法簡潔,適合初學者。

PHP行動:現實世界中的示例和應用程序 PHP行動:現實世界中的示例和應用程序 Apr 14, 2025 am 12:19 AM

PHP在電子商務、內容管理系統和API開發中廣泛應用。 1)電子商務:用於購物車功能和支付處理。 2)內容管理系統:用於動態內容生成和用戶管理。 3)API開發:用於RESTfulAPI開發和API安全性。通過性能優化和最佳實踐,PHP應用的效率和可維護性得以提升。

PHP:網絡開發的關鍵語言 PHP:網絡開發的關鍵語言 Apr 13, 2025 am 12:08 AM

PHP是一種廣泛應用於服務器端的腳本語言,特別適合web開發。 1.PHP可以嵌入HTML,處理HTTP請求和響應,支持多種數據庫。 2.PHP用於生成動態網頁內容,處理表單數據,訪問數據庫等,具有強大的社區支持和開源資源。 3.PHP是解釋型語言,執行過程包括詞法分析、語法分析、編譯和執行。 4.PHP可以與MySQL結合用於用戶註冊系統等高級應用。 5.調試PHP時,可使用error_reporting()和var_dump()等函數。 6.優化PHP代碼可通過緩存機制、優化數據庫查詢和使用內置函數。 7

PHP的持久相關性:它還活著嗎? PHP的持久相關性:它還活著嗎? Apr 14, 2025 am 12:12 AM

PHP仍然具有活力,其在現代編程領域中依然佔據重要地位。 1)PHP的簡單易學和強大社區支持使其在Web開發中廣泛應用;2)其靈活性和穩定性使其在處理Web表單、數據庫操作和文件處理等方面表現出色;3)PHP不斷進化和優化,適用於初學者和經驗豐富的開發者。

PHP與Python:了解差異 PHP與Python:了解差異 Apr 11, 2025 am 12:15 AM

PHP和Python各有優勢,選擇應基於項目需求。 1.PHP適合web開發,語法簡單,執行效率高。 2.Python適用於數據科學和機器學習,語法簡潔,庫豐富。

PHP和Python:代碼示例和比較 PHP和Python:代碼示例和比較 Apr 15, 2025 am 12:07 AM

PHP和Python各有優劣,選擇取決於項目需求和個人偏好。 1.PHP適合快速開發和維護大型Web應用。 2.Python在數據科學和機器學習領域佔據主導地位。

PHP與其他語言:比較 PHP與其他語言:比較 Apr 13, 2025 am 12:19 AM

PHP適合web開發,特別是在快速開發和處理動態內容方面表現出色,但不擅長數據科學和企業級應用。與Python相比,PHP在web開發中更具優勢,但在數據科學領域不如Python;與Java相比,PHP在企業級應用中表現較差,但在web開發中更靈活;與JavaScript相比,PHP在後端開發中更簡潔,但在前端開發中不如JavaScript。

PHP和Python:解釋了不同的範例 PHP和Python:解釋了不同的範例 Apr 18, 2025 am 12:26 AM

PHP主要是過程式編程,但也支持面向對象編程(OOP);Python支持多種範式,包括OOP、函數式和過程式編程。 PHP適合web開發,Python適用於多種應用,如數據分析和機器學習。

See all articles