成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

PHP 算法 —— 歸并排序

leoperfect / 3064人閱讀

摘要：算法原理下列動圖來自五分鐘學算法，演示了歸并算法的原理和步驟。原理利用遞歸，先拆分后合并再排序。假設被排序的數(shù)列中有個數(shù)。參考資料歸并排序十大經典排序算法動畫與解析感謝您的閱讀，覺得內容不錯，點個贊吧

算法原理

下列動圖來自@五分鐘學算法，演示了歸并算法的原理和步驟。

原理:

利用遞歸，先拆分、后合并、再排序。

步驟:

均分數(shù)列為兩個子數(shù)列

遞歸重復上一步驟，直到子數(shù)列只有一個元素

父數(shù)列合并兩個子數(shù)列并排序，遞歸返回數(shù)列

代碼實現(xiàn) 
// 歸并排序主程序
function mergeSort($arr) {
    $len = count($arr);
    if ($len <= 1) {
        return $arr;
    } // 遞歸結束條件, 到達這步的時候, 數(shù)組就只剩下一個元素了, 也就是分離了數(shù)組

    $mid = intval($len / 2); // 取數(shù)組中間
    $left = array_slice($arr, 0, $mid); // 拆分數(shù)組0-mid這部分給左邊left
    $right = array_slice($arr, $mid); // 拆分數(shù)組mid-末尾這部分給右邊right
    $left = mergeSort($left); // 左邊拆分完后開始遞歸合并往上走
    $right = mergeSort($right); // 右邊拆分完畢開始遞歸往上走
    $arr = merge($left, $right); // 合并兩個數(shù)組,繼續(xù)遞歸

    return $arr;
}

// merge函數(shù)將指定的兩個有序數(shù)組(arrA, arr)合并并且排序
function merge($arrA, $arrB) {
    $arrC = array();
    while (count($arrA) && count($arrB)) {
        // 這里不斷的判斷哪個值小, 就將小的值給到arrC, 但是到最后肯定要剩下幾個值,
        // 不是剩下arrA里面的就是剩下arrB里面的而且這幾個有序的值, 肯定比arrC里面所有的值都大所以使用
        $arrC[] = $arrA[0] < $arrB[0] ? array_shift($arrA) : array_shift($arrB);
    }

    return array_merge($arrC, $arrA, $arrB);
}

測試:

$startTime = microtime(1);

$arr = range(1, 10);
shuffle($arr);

echo "before sort: ", implode(", ", $arr), "
";
$sortArr = mergeSort($arr);
echo "after sort: ", implode(", ", $sortArr), "
";

echo "use time: ", microtime(1) - $startTime, "s
";
時間復雜度

歸并排序的時間復雜度是 O(N*lgN)。

假設被排序的數(shù)列中有 N 個數(shù)。遍歷一趟的時間復雜度是 O(N)，需要遍歷多少次呢？

歸并排序的形式就是一棵二叉樹，它需要遍歷的次數(shù)就是二叉樹的深度，而根據(jù)完全二叉樹的可以得出它的時間復雜度是 O(N*lgN)。

參考資料

歸并排序

十大經典排序算法動畫與解析

感謝您的閱讀，覺得內容不錯，點個贊吧

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://systransis.cn/yun/30108.html

相關文章

  • PHP面試：盡可能多的說出你知道的排序算法

    摘要：良好的排序算法具有進行最少的比較和交換的特征。冒泡排序是一個基于比較的排序算法，被認為是效率最低的排序算法之一?，F(xiàn)在讓我們使用實現(xiàn)冒泡排序算法。插入排序到目前為止，我們已經看到了兩種基于比較的排序算法。 預警 本文適合對于排序算法不太了解的新手同學觀看，大佬直接忽略即可。因為考慮到連貫性，所以篇幅較長。老鐵們看完需要大概一個小時，但是從入門到完全理解可能需要10個小時(哈哈哈，以我自己...

    objc94 評論0 收藏0

  • PHP面試之四：邏輯與算法

    摘要：數(shù)據(jù)結構常見數(shù)據(jù)結構數(shù)組是最簡單而且應用最廣泛的數(shù)據(jù)結構特征使用連續(xù)內存空間來存儲存放相同類型或著衍生類型的元素數(shù)組比較特別，可以存放八種數(shù)據(jù)類型通過下標來訪問集合特征保存不重復的元素字典特征就是關聯(lián)數(shù)組，以形式存儲棧，與隊列相似特征存儲數(shù) 數(shù)據(jù)結構 常見數(shù)據(jù)結構 Array 數(shù)組是 最簡單 而且 應用最廣泛 的數(shù)據(jù)結構 特征： 1、使用連續(xù)內存空間來存儲 2、存放相同類型或著衍生類型...

    smartlion 評論0 收藏0

  • 歸并排序 - Algorithms, Part I, week 3 MERGESORTS

    摘要：兩個單元素數(shù)組的合并實際就是對這兩個數(shù)進行了排序，即變?yōu)椋瑯釉賹笠唤M的兩個數(shù)歸并排序，即變?yōu)?，再將兩單元?shù)組歸并成四單元數(shù)組即和歸并為。 前言 本周講解兩個50多年前發(fā)明，但今天仍然很重要的經典算法 (歸并排序和快速排序) 之一 -- 歸并排序，幾乎每個軟件系統(tǒng)中都可以找到其中一個或兩個的實現(xiàn)，并研究這些經典方法的新變革。我們的涉及范圍從數(shù)學模型中解釋為什么這些方法有效到使這些算法...

    Jokcy 評論0 收藏0

  • JavaScript算法 ,Python算法,Go算法,java算法,系列之歸并排序

    摘要：常見的內部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數(shù)排序等。用一張圖概括歸并排序英語，或，是創(chuàng)建在歸并操作上的一種有效的排序算法，效率為。 常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。用一張圖概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

    zhou_you 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<