PHP 快速排序演算法原理與實作完整解析

PHP 快速排序演算法原理與實作完整解析

快速排序是對氣泡排序的改進，基本思想：透過一趟排序將資料分割成獨立兩部分，一部分所有資料皆比另一部分小，再遞迴對兩部分分別快速排序，最終形成有序序列。

演算法步驟

1. 設定兩個變數 I、J，初始 I=1、J=N。
2. 以第一個元素為基準值 X = A[1]。
3. 從 J 向前搜尋（J--），找到第一個小於 X 的值，與 I 位置交換。
4. 從 I 向後搜尋（I++），找到第一個大於 X 的值，與 J 位置交換。
5. 重複步驟 3、4 直到 I=J，完成一趟分割。
6. 遞迴對左右子陣列執行相同過程。

PHP 實作範例

<?php
$n = array('13','14','55','10','54','2','79','106','89','90','22','60','111','77777','-110','-10','123');

function partition(&$arr, $left, $right) {
    $pivot = $arr[$left];
    $lo = $left;
    $hi = $right + 1;
    while ($lo + 1 != $hi) {
        if ($arr[$lo + 1] < $pivot) {
            $lo++;
        } elseif ($arr[$hi - 1] > $pivot) {
            $hi--;
        } else {
            $t = $arr[$lo + 1];
            $arr[$lo + 1] = $arr[$hi - 1];
            $arr[$hi - 1] = $t;
            $lo++;
            $hi--;
        }
    }
    $arr[$left] = $arr[$lo];
    $arr[$lo] = $pivot;
    return $lo;
}

function quicksort(&$arr, $left, $right) {
    if ($left < $right) {
        $dp = partition($arr, $left, $right);
        quicksort($arr, $left, $dp - 1);
        quicksort($arr, $dp + 1, $right);
    }
}

quicksort($n, 0, sizeof($n) - 1);
print_r($n);
?>

補充工具推薦：

• PHP 程式碼線上格式化美化工具： https://tools.jb51.net/code/phpformat
• C 語言風格/HTML/CSS/JSON 程式碼格式化美化工具： https://tools.jb51.net/code/ccode_html_css_json

更多 PHP 相關內容請參考本站專題：《PHP 陣列操作技巧大全》、《PHP 排序演算法總結》、《PHP 常用遍歷演算法與技巧總結》、《PHP 資料結構與演算法教程》、《PHP 程式設計演算法總結》、《PHP 數學運算技巧總結》、《PHP 正則表達式用法總結》、《PHP 運算與運算子用法總結》、《PHP 字串用法總結》及《PHP 常見資料庫操作技巧匯總》。

希望本文能對您的 PHP 程式設計有所幫助。