目錄
基本思想:
基本演算法步驟:
演算法實作:
複雜度分析:
首頁 後端開發 PHP問題 php如何實現快速排序

php如何實現快速排序

Oct 19, 2020 am 11:23 AM
php 快速排序

php實作快速排序的方法:先建立一個PHP範例檔;然後建立交換函數和主函數;接著對低子表和高子表進行遞歸排序;最後呼叫QuickSort演算法即可。

php如何實現快速排序

#推薦:《PHP影片教學

基本思想:

快速排序(Quicksort)是對冒泡排序的一種改進。他的基本想法是:透過一趟排序將待排記錄分割成獨立的兩部分,其中一部分的關鍵字均比另一部分記錄的關鍵字小,則可分別對這兩部分記錄繼續進行快速排序,整個排序過程可以遞歸進行,以達到整個序列有序的目的​​。

基本演算法步驟:

舉個栗子:
php如何實現快速排序

假如現在待排序記錄是:

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中文網其他相關文章!

本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

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

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

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

適用於 Ubuntu 和 Debian 的 PHP 8.4 安裝和升級指南 適用於 Ubuntu 和 Debian 的 PHP 8.4 安裝和升級指南 Dec 24, 2024 pm 04:42 PM

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

我後悔之前不知道的 7 個 PHP 函數 我後悔之前不知道的 7 個 PHP 函數 Nov 13, 2024 am 09:42 AM

如果您是經驗豐富的PHP 開發人員,您可能會感覺您已經在那裡並且已經完成了。操作

如何設定 Visual Studio Code (VS Code) 進行 PHP 開發 如何設定 Visual Studio Code (VS Code) 進行 PHP 開發 Dec 20, 2024 am 11:31 AM

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

在PHP API中說明JSON Web令牌(JWT)及其用例。 在PHP API中說明JSON Web令牌(JWT)及其用例。 Apr 05, 2025 am 12:04 AM

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

php程序在字符串中計數元音 php程序在字符串中計數元音 Feb 07, 2025 pm 12:12 PM

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

您如何在PHP中解析和處理HTML/XML? 您如何在PHP中解析和處理HTML/XML? Feb 07, 2025 am 11:57 AM

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

解釋PHP中的晚期靜態綁定(靜態::)。 解釋PHP中的晚期靜態綁定(靜態::)。 Apr 03, 2025 am 12:04 AM

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

什麼是PHP魔術方法(__ -construct,__destruct,__call,__get,__ set等)並提供用例? 什麼是PHP魔術方法(__ -construct,__destruct,__call,__get,__ set等)並提供用例? Apr 03, 2025 am 12:03 AM

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

See all articles