成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

PHP 算法 —— 歸并排序

leoperfect / 3110人閱讀

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

算法原理

下列動(dòng)圖來自@五分鐘學(xué)算法，演示了歸并算法的原理和步驟。

原理:

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

步驟:

均分?jǐn)?shù)列為兩個(gè)子數(shù)列

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

父數(shù)列合并兩個(gè)子數(shù)列并排序，遞歸返回?cái)?shù)列

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

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

    return $arr;
}

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

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

測(cè)試:

$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
";
時(shí)間復(fù)雜度

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

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

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

參考資料

歸并排序

十大經(jīng)典排序算法動(dòng)畫與解析

感謝您的閱讀，覺得內(nèi)容不錯(cuò)，點(diǎn)個(gè)贊吧

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/30108.html

相關(guān)文章

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

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

    objc94 評(píng)論0 收藏0

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

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

    smartlion 評(píng)論0 收藏0

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

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

    Jokcy 評(píng)論0 收藏0

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

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

    zhou_you 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<