PHP 實(shí)現(xiàn)快速排序

Loong_T 發(fā)布于2019-07-01 11:15 / 2494人閱讀

摘要：導(dǎo)語(yǔ)這篇了解下快速排序。事實(shí)上，快速排序通常明顯比其他算法更快，因?yàn)樗膬?nèi)部循環(huán)可以在大部分的架構(gòu)上很有效率地達(dá)成。動(dòng)圖演示實(shí)例基準(zhǔn)值小于基準(zhǔn)值，存入左邊大于基準(zhǔn)值，存入右邊倒序參考資料快速排序快速排序算法演示排序算法。

導(dǎo)語(yǔ)

這篇了解下快速排序。

快速排序

快速排序（英語(yǔ)：Quicksort），又稱劃分交換排序（partition-exchange sort），簡(jiǎn)稱快排，一種排序算法，最早由東尼·霍爾提出。在平均狀況下，排序 n 個(gè)項(xiàng)目要 O(n log n) 次比較。在最壞狀況下則需要 O(n²) 次比較，但這種狀況并不常見(jiàn)。事實(shí)上，快速排序 O(n log n) 通常明顯比其他算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地達(dá)成。
步驟為：

從數(shù)列中挑出一個(gè)元素，稱為"基準(zhǔn)"（pivot），
重新排序數(shù)列，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面（相同的數(shù)可以到任何一邊）。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作。

遞歸地（recursively）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。

遞歸到最底部時(shí)，數(shù)列的大小是零或一，也就是已經(jīng)排序好了。這個(gè)算法一定會(huì)結(jié)束，因?yàn)樵诿看蔚牡╥teration）中，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。

維基百科中的介紹。核心的思想是使用遞歸，下面的動(dòng)圖很形象。

動(dòng)圖演示

實(shí)例

 2 [1] => 3 [2] => 8 [3] => 16 [4] => 21 [5] => 23 [6] => 24 [7] => 32 [8] => 33 )

參考資料：快速排序、PHP 快速排序算法、GIF演示排序算法。

云服務(wù)器 GPU云服務(wù)器 php快速排序用php實(shí)現(xiàn)插入排序快速排序快速排序函數(shù)

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/30024.html

相關(guān)文章

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

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

shleyZ 2019-06-28 18:31 評(píng)論0 收藏0
PHP 快速排序算法

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

Coly 2019-06-27 10:56 評(píng)論0 收藏0
PHP 算法 —— 快速排序

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

Apollo 2019-07-01 12:38 評(píng)論0 收藏0
利用PHP實(shí)現(xiàn)常用的數(shù)據(jù)結(jié)構(gòu)之排序（小白系列文章七）

摘要：排序嚴(yán)格來(lái)說(shuō)不算數(shù)據(jù)結(jié)構(gòu)，更應(yīng)該歸于算法一類，因?yàn)閿?shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)與數(shù)據(jù)之間的關(guān)系，排序參與其中，更多的是讓數(shù)據(jù)狀態(tài)發(fā)生了改變。排序嚴(yán)格來(lái)說(shuō)不算數(shù)據(jù)結(jié)構(gòu)，更應(yīng)該歸于算法一類，因?yàn)閿?shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)與數(shù)據(jù)之間的關(guān)系，排序參與其中，更多的是讓數(shù)據(jù)狀態(tài)發(fā)生了改變。于是，我們開(kāi)始用PHP來(lái)聊聊算法。引子其實(shí)有一句話說(shuō)的是不錯(cuò)的，不必重復(fù)造輪子，所以下面我將引用別人的文章作為本文的引文，...

jayzou 2019-06-28 13:56 評(píng)論0 收藏0
[討論]php 排序系列的函數(shù)內(nèi)部的C實(shí)現(xiàn)是用了哪種排序算法？

摘要：在算法中，比快速排序還快的，無(wú)疑是基數(shù)排序，粗略看了一下算法，可能是基礎(chǔ)排序中的桶排序。桶排序是穩(wěn)定的桶排序是常見(jiàn)排序里最快的一種，比快排還要快大多數(shù)情況下桶排序非?？欤峭瑫r(shí)也非常耗空間以空間換時(shí)間 ext/standard/php_array.h https://github.com/php/php-src/blob/master/ext/standard/php_array....

chanthuang 2019-06-27 10:27 評(píng)論0 收藏0