首頁  >  文章  >  後端開發  >  PHP排序演算法系列之歸併排序詳解_php技巧

PHP排序演算法系列之歸併排序詳解_php技巧

jacklove
jacklove原創
2018-07-03 17:53:592122瀏覽

這篇文章主要為大家詳細介紹了PHP排序演算法系列之歸併排序的相關資料,具有一定的參考價值,有興趣的小伙伴們可以參考一下

##歸併排序

歸併排序(MERGE-SORT)是建立在歸併操作上的一種有效的排序演算法,該演算法是採用分治法(pide and Conquer)的一個非常典型的應用。將已有序的子序列合併,得到完全有序的序列;即先使每個子序列有序,再使子序列段間有序。若將兩個有序表合併成一個有序表,稱為二路歸併。

歸併過程

歸併排序的核心就是如何將兩個有序序列合併,假定有兩個有序數組,比較兩個有序數組的首個元素,誰小就取誰,並將該元素放入第三個數組中,取了之後在相應的數組中將刪除此元素,依次類推,當取到一個數組已經沒有元素時,就可將另一數組的剩餘元素直接加入第三個數組中。

原理

1、將序列每相鄰兩個數字進行歸併操作,形成ceil(n/2)個序列,排序後每個序列包含兩個元素,最後一個序列可能只有一個元素。


2、將上述序列再次歸併,形成ceil(n/4)個序列,每個序列包含四個元素,最後一個序列可能只有三個及以下元素。


3、重複步驟2,直到所有元素都排序完畢。


範例

對陣列[53,89,12,6,98,25,37,92,5]進行排序

#第一次歸併後

(53,89),12,(6,98),(25,37),(5,92)

第二次歸併後

(12,53,89),(6,25,37,98),(5,92)

第三次歸併後

(6,12,25 ,37,53,89,98),(5,92)

第四次歸併後

5,6,12,25,37,53,89,92,98

PHP程式碼實作


<?php
function merge_sort($arr){
  $length=count($arr);
  if($length<=1){
    return $arr;
  }
  //分解数组,递归排序
  $half=ceil($length/2);
  $arr2=array_chunk($arr,$half);
  $left=merge_sort($arr2[0]);
  $right=merge_sort($arr2[1]);
  while(count($left)&&count($right)){
    if($left[0]<$right[0]){
      $reg[]=array_shift($left);
    }else{
      $reg[]=array_shift($right);
    }
  }
  return array_merge($reg,$left,$right);
}


#以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持php中文網。


您可能感興趣的文章:

PHP排序演算法系列之直接選擇排序的詳解

PHP排序演算法系列之插入排序的詳解

#PHP實作桶排序演算法的講解

以上是PHP排序演算法系列之歸併排序詳解_php技巧的詳細內容。更多資訊請關注PHP中文網其他相關文章!

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