php如何實現快速排序
php實作快速排序的方法:先建立一個PHP範例檔;然後建立交換函數和主函數;接著對低子表和高子表進行遞歸排序;最後呼叫QuickSort演算法即可。
#推薦:《PHP影片教學》
基本思想:
快速排序(Quicksort)是對冒泡排序的一種改進。他的基本想法是:透過一趟排序將待排記錄分割成獨立的兩部分,其中一部分的關鍵字均比另一部分記錄的關鍵字小,則可分別對這兩部分記錄繼續進行快速排序,整個排序過程可以遞歸進行,以達到整個序列有序的目的。
基本演算法步驟:
舉個栗子:
假如現在待排序記錄是:
6 2 7 3 8 9
第一步、建立變數$low 指向記錄中的第一個記錄,$high 指向最後一個記錄,$pivot 作為樞軸賦值為待排序記錄的第一個元素(不一定是第一個),這裡:
$low = 0; $high = 5; $pivot = 6;
第二步、我們要把所有比$pivot 小的數移動到$pivot 的左面,所以我們可以開始尋找比6小的數,從$high 開始,從右往左找,不斷遞減變數$high 的值,我們找到第一個下標3 的資料比6 小,於是把資料3 移到下標0 的位置($low 指向的位置),把下標0 的資料6 移到下標3,完成第一次比較:
3 2 7 6 8 9 //这时候,$high 减小为 3 $low = 0; $high = 3; $pivot = 6;
第三步、我們開始第二次比較,這次要變成找比$pivot 大的了,而且要從前往後找了。遞加變數$low,發現下標2 的資料是第一個比$pivot 大的,於是用下標2 ($low 指向的位置)的資料7 和指向的下標3 ($high 指向的位置)的資料的6 做交換,資料狀態變成下表:
3 2 6 7 8 9 //这时候,$high 减小为 3 $low = 2; $high = 3; $pivot = 6;
完成第二步和第三步我們稱為完成一個迴圈。
第四步(也就是開啟下一個迴圈)、模仿第二步的過程執行。
第五步、模仿第三步的過程執行。
執行完第二個循環之後,資料狀態如下:
3 2 6 7 8 9 //这时候,$high 减小为 3 $low = 2; $high = 2; $pivot = 6;
到了這一步,我們發現 $low 和 $high「碰頭」了:他們都指向了下標 2。於是,第一遍比較結束。得到結果如下,凡是 $pivot(=6) 左邊的數都比它小,凡是 $pivot 右邊的數都比它大。
然後,將 、$pivot 兩邊的資料 {3,2} 和 {7,8,9},再分組分別進行上述的過程,直到不能再分組為止。
注意:第一遍快速排序不會直接得到最終結果,只會把比k大和比k小的數分到k的兩邊。為了得到最後結果,需要再次對下標2兩邊的陣列分別執行此步驟,然後再分解數組,直到數組不能再分解為止(只有一個資料),才能得到正確結果。
演算法實作:
//交换函数 function swap(array &$arr,$a,$b){ $temp = $arr[$a]; $arr[$a] = $arr[$b]; $arr[$b] = $temp; } //主函数: function QuickSort(array &$arr){ $low = 0; $high = count($arr) - 1; QSort($arr,$low,$high); }
主函數中,由於第一遍快速排序是對整個陣列排序的,因此開始是$low=0,$high=count($arr)- 1。
然後QSort() 函數是個遞歸呼叫過程,因此對它封裝了一下:
function QSort(array &$arr,$low,$high){ //当 $low >= $high 时表示不能再进行分组,已经能够得出正确结果了 if($low < $high){ $pivot = Partition($arr,$low,$high); //将$arr[$low...$high]一分为二,算出枢轴值 QSort($arr,$low,$pivot - 1); //对低子表($pivot左边的记录)进行递归排序 QSort($arr,$pivot + 1,$high); //对高子表($pivot右边的记录)进行递归排序 } }
從上面的QSort()函數中我們看出,Partition()函數才是整段程式碼的核心,因為函數的功能是:選取當中的一個關鍵字,例如選擇第一個關鍵字。然後想盡辦法將它放到某個位置,使得它左邊的值都比它小,右邊的值都比它大,我們將這樣的關鍵字成為樞軸(pivot)。
直接上程式碼:
//选取数组当中的一个关键字,使得它处于数组某个位置时,左边的值比它小,右边的值比它大,该关键字叫做枢轴 //使枢轴记录到位,并返回其所在位置 function Partition(array &$arr,$low,$high){ $pivot = $arr[$low]; //选取子数组第一个元素作为枢轴 while($low < $high){ //从数组的两端交替向中间扫描(当 $low 和 $high 碰头时结束循环) while($low < $high && $arr[$high] >= $pivot){ $high --; } swap($arr,$low,$high); //终于遇到一个比$pivot小的数,将其放到数组低端 while($low < $high && $arr[$low] <= $pivot){ $low ++; } swap($arr,$low,$high); //终于遇到一个比$pivot大的数,将其放到数组高端 } return $low; //返回high也行,毕竟最后low和high都是停留在pivot下标处 }
組合起來的整個程式碼如下:
function swap(array &$arr,$a,$b){ $temp = $arr[$a]; $arr[$a] = $arr[$b]; $arr[$b] = $temp; } function Partition(array &$arr,$low,$high){ $pivot = $arr[$low]; //选取子数组第一个元素作为枢轴 while($low < $high){ //从数组的两端交替向中间扫描 while($low < $high && $arr[$high] >= $pivot){ $high --; } swap($arr,$low,$high); //终于遇到一个比$pivot小的数,将其放到数组低端 while($low < $high && $arr[$low] <= $pivot){ $low ++; } swap($arr,$low,$high); //终于遇到一个比$pivot大的数,将其放到数组高端 } return $low; //返回high也行,毕竟最后low和high都是停留在pivot下标处 } function QSort(array &$arr,$low,$high){ if($low < $high){ $pivot = Partition($arr,$low,$high); //将$arr[$low...$high]一分为二,算出枢轴值 QSort($arr,$low,$pivot - 1); //对低子表进行递归排序 QSort($arr,$pivot + 1,$high); //对高子表进行递归排序 } } function QuickSort(array &$arr){ $low = 0; $high = count($arr) - 1; QSort($arr,$low,$high); }
我們呼叫演算法:
$arr = array(9,1,5,8,3,7,4,6,2); QuickSort($arr); var_dump($arr);
複雜度分析:
在最優的情況下,也就是選擇數軸處於整個數組的中間值的話,則每一次就會不斷將數組平分為兩半。因此最優情況下的時間複雜度是 O(nlogn) (跟堆排序、歸併排序一樣)。
最壞的情況下,待排序的序列是正序或逆序的,那麼在選擇樞軸的時候只能選到邊緣數據,每次劃分得到的比上一次劃分少一個記錄,另一個分為空,這樣的情況的最終時間複雜度為O(n^2).
綜合最適與最差情況,平均的時間複雜度是O(nlogn).
快速排序是一種不穩定排序方法。
由於快速排序是個比較進階的排序,而且被列為20世紀十大演算法之一。 。 。 。如此牛掰的演算法,我們還有什麼理由不去學他呢!
儘管這個演算法已經很牛了,但是上面的演算法程式依然有改進的地方。
#以上是php如何實現快速排序的詳細內容。更多資訊請關注PHP中文網其他相關文章!

熱AI工具

Undresser.AI Undress
人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

Video Face Swap
使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱門文章

熱工具

記事本++7.3.1
好用且免費的程式碼編輯器

SublimeText3漢化版
中文版,非常好用

禪工作室 13.0.1
強大的PHP整合開發環境

Dreamweaver CS6
視覺化網頁開發工具

SublimeText3 Mac版
神級程式碼編輯軟體(SublimeText3)

PHP 8.4 帶來了多項新功能、安全性改進和效能改進,同時棄用和刪除了大量功能。 本指南介紹如何在 Ubuntu、Debian 或其衍生版本上安裝 PHP 8.4 或升級到 PHP 8.4

Visual Studio Code,也稱為 VS Code,是一個免費的原始碼編輯器 - 或整合開發環境 (IDE) - 可用於所有主要作業系統。 VS Code 擁有大量針對多種程式語言的擴展,可以輕鬆編寫

JWT是一種基於JSON的開放標準,用於在各方之間安全地傳輸信息,主要用於身份驗證和信息交換。 1.JWT由Header、Payload和Signature三部分組成。 2.JWT的工作原理包括生成JWT、驗證JWT和解析Payload三個步驟。 3.在PHP中使用JWT進行身份驗證時,可以生成和驗證JWT,並在高級用法中包含用戶角色和權限信息。 4.常見錯誤包括簽名驗證失敗、令牌過期和Payload過大,調試技巧包括使用調試工具和日誌記錄。 5.性能優化和最佳實踐包括使用合適的簽名算法、合理設置有效期、

字符串是由字符組成的序列,包括字母、數字和符號。本教程將學習如何使用不同的方法在PHP中計算給定字符串中元音的數量。英語中的元音是a、e、i、o、u,它們可以是大寫或小寫。 什麼是元音? 元音是代表特定語音的字母字符。英語中共有五個元音,包括大寫和小寫: a, e, i, o, u 示例 1 輸入:字符串 = "Tutorialspoint" 輸出:6 解釋 字符串 "Tutorialspoint" 中的元音是 u、o、i、a、o、i。總共有 6 個元

本教程演示瞭如何使用PHP有效地處理XML文檔。 XML(可擴展的標記語言)是一種用於人類可讀性和機器解析的多功能文本標記語言。它通常用於數據存儲

靜態綁定(static::)在PHP中實現晚期靜態綁定(LSB),允許在靜態上下文中引用調用類而非定義類。 1)解析過程在運行時進行,2)在繼承關係中向上查找調用類,3)可能帶來性能開銷。

PHP的魔法方法有哪些? PHP的魔法方法包括:1.\_\_construct,用於初始化對象;2.\_\_destruct,用於清理資源;3.\_\_call,處理不存在的方法調用;4.\_\_get,實現動態屬性訪問;5.\_\_set,實現動態屬性設置。這些方法在特定情況下自動調用,提升代碼的靈活性和效率。
