PHP 算法 —— 快速排序

Apollo 發布于2019-07-01 12:38 / 2662人閱讀

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

算法原理

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

步驟:

從數組中選個基準值

將數組中大于基準值的放同一邊、小于基準值的放另一邊，基準值位于中間位置

遞歸的對分列兩邊的數組再排序

代碼實現

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);
}

測試代碼:

$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
";

測試結果:

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

時間復雜度

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

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

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

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

參考資料

快速排序

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

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

云服務器 GPU云服務器快速排序算法最好的快速排序算法最快速的排序算法 php快速排序

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/31141.html

php 經典排序算法（解析）

摘要：介紹三種排序算法快速排序選擇排序冒泡排序選擇排序選擇排序是一種簡單直觀的排序算法。介紹三種排序算法快速排序選擇排序冒泡排序選擇排序選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理是每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。選擇排序是不穩定的排序方法（比如序列[5， 5， 3...

FuisonDesign 2019-06-28 14:08 評論0 收藏0
PHP 快速排序算法

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

Coly 2019-06-27 10:56 評論0 收藏0
快速排序算法圖解與PHP實現講解

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

shleyZ 2019-06-28 18:31 評論0 收藏0
PHP算法之四大基礎算法

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

isLishude 2019-07-01 12:31 評論0 收藏0
PHP面試：盡可能多的說出你知道的排序算法

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

objc94 2019-07-01 10:39 評論0 收藏0