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

資訊專欄INFORMATION COLUMN

PHP 算法 —— 快速排序

Apollo / 2672人閱讀

摘要：算法原理下列動(dòng)圖來自五分鐘學(xué)算法，演示了快速排序算法的原理和步驟。因此，快速排序的遍歷次數(shù)最少是次。為什么最多是次這個(gè)應(yīng)該非常簡(jiǎn)單，還是將快速排序看作一棵二叉樹，它的深度最大是。

算法原理

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

步驟:

從數(shù)組中選個(gè)基準(zhǔn)值

將數(shù)組中大于基準(zhǔn)值的放同一邊、小于基準(zhǔn)值的放另一邊，基準(zhǔn)值位于中間位置

遞歸的對(duì)分列兩邊的數(shù)組再排序

代碼實(shí)現(xiàn) 
function quickSort($arr)
{
    $len = count($arr);
    if ($len <= 1) {
        return $arr;
    }

    $v = $arr[0];
    $low = $up = array();
    for ($i = 1; $i < $len; ++$i) {
        if ($arr[$i] > $v) {
            $up[] = $arr[$i];
        } else {
            $low[] = $arr[$i];
        }
    }
    $low = quickSort($low);
    $up = quickSort($up);

    return array_merge($low, array($v), $up);
}

測(cè)試代碼:

$startTime = microtime(1);

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

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

echo "use time: ", microtime(1) - $startTime, "s
";

測(cè)試結(jié)果:

before sort: 1, 7, 10, 9, 6, 3, 2, 5, 4, 8
after sort: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
use time: 0.0009009838104248s
時(shí)間復(fù)雜度

快速排序的時(shí)間復(fù)雜度在最壞情況下是O(N2)，平均的時(shí)間復(fù)雜度是O(N*lgN)。

這句話很好理解：假設(shè)被排序的數(shù)列中有N個(gè)數(shù)。遍歷一次的時(shí)間復(fù)雜度是O(N)，需要遍歷多少次呢？至少lg(N+1)次，最多N次。

1) 為什么最少是lg(N+1)次？快速排序是采用的分治法進(jìn)行遍歷的，我們將它看作一棵二叉樹，它需要遍歷的次數(shù)就是二叉樹的深度，而根據(jù)完全二叉樹的定義，它的深度至少是lg(N+1)。因此，快速排序的遍歷次數(shù)最少是lg(N+1)次。

2) 為什么最多是N次？這個(gè)應(yīng)該非常簡(jiǎn)單，還是將快速排序看作一棵二叉樹，它的深度最大是N。因此，快讀排序的遍歷次數(shù)最多是N次。

參考資料

快速排序

十大經(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://systransis.cn/yun/31141.html

相關(guān)文章

  • php 經(jīng)典排序算法（解析）

    摘要：介紹三種排序算法快速排序選擇排序冒泡排序選擇排序選擇排序是一種簡(jiǎn)單直觀的排序算法。 介紹三種排序算法 快速排序 選擇排序 冒泡排序 選擇排序 選擇排序（Selection sort）是一種簡(jiǎn)單直觀的排序算法。它的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。 選擇排序是不穩(wěn)定的排序方法（比如序列[5， 5， 3...

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

  • PHP 快速排序算法

    摘要：概念這里借用百度百科的一張圖來，非常形象快速排序算法是對(duì)冒泡算法的一個(gè)優(yōu)化。獲取已經(jīng)打亂了順序的數(shù)組快速排序這里引用的是我之前寫的冒泡算法排序冒泡運(yùn)行結(jié)果 概念 這里借用百度百科的一張圖來，非常形象：showImg(https://segmentfault.com/img/bVdlR6); 快速排序算法是對(duì)冒泡算法的一個(gè)優(yōu)化。他的思想是先對(duì)數(shù)組進(jìn)行分割， 把大的元素?cái)?shù)值放到一個(gè)臨時(shí)數(shù)...

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

  • 快速排序算法圖解與PHP實(shí)現(xiàn)講解

    摘要：概述快速排序最初由東尼霍爾提出，是一種平均時(shí)間復(fù)雜度為，最差時(shí)間復(fù)雜度為的排序算法。測(cè)試算法效率與復(fù)雜度完全隨機(jī)序列排序結(jié)果以下面的方法分別生成元素個(gè)數(shù)為萬萬的完全隨機(jī)數(shù)組，并用快速排序算法對(duì)其排序。 概述 快速排序（QuickSort）最初由東尼·霍爾提出，是一種平均時(shí)間復(fù)雜度為showImg(https://segmentfault.com/img/bV5sdO?w=61&h=17...

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

  • PHP算法之四大基礎(chǔ)算法

    摘要：而在證明算法是正確的基礎(chǔ)上，第二步就是分析算法的時(shí)間復(fù)雜度。算法的時(shí)間復(fù)雜度反映了程序執(zhí)行時(shí)間隨輸入規(guī)模增長(zhǎng)而增長(zhǎng)的量級(jí)，在很大程度上能很好反映出算法的優(yōu)劣與否。 showImg(https://segmentfault.com/img/remote/1460000016451712?w=800&h=341); 前言 雖然工作中，你覺得自己并沒有涉及到算法這方面的東西，但是算法是程序的...

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

  • 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

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

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<