PHP 陣列快排 vs. 歸併排序

快排是一種遞歸演算法，將陣列分成較小元素和較大元素兩部分並遞歸排序，而歸併排序將陣列遞歸地分成較小的數組，對每個小數組排序，再合併回原始數組。 PHP 實作的程式碼分別為：快排：將陣列分成小於和大於基準值的元素，然後將每個部分遞歸排序。歸併排序：將數組遞歸地分成較小的數組，對每個較小的數組排序，然後將排序後的較小的數字組合併回原始數組。

PHP 陣列快排 vs. 歸併排序

什麼是快排和歸併排序？

快排和歸併排序都是用來對陣列進行排序的常見演算法。

• 快排：將陣列分成兩個部分，一個包含較小的元素，另一個包含較大的元素，然後遞歸地對每個部分排序。
• 歸併排序：將數組遞歸地分成較小的數組，對每個較小的數組排序，然後將排序後的較小的數組合併回原始數組。

程式碼實作

以下是用PHP 實作的快排和歸併排序函數：

##快排：

function quickSort($arr) {
    if (count($arr) <= 1) {
        return $arr;
    }
    $pivot = $arr[0];
    $left = [];
    $right = [];
    for ($i = 1; $i < count($arr); $i++) {
        if ($arr[$i] < $pivot) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }
    return array_merge(quickSort($left), [$pivot], quickSort($right));
}

歸併排序：

function mergeSort($arr) {
    $length = count($arr);
    if ($length <= 1) {
        return $arr;
    }
    $mid = floor($length / 2);
    $left = array_slice($arr, 0, $mid);
    $right = array_slice($arr, $mid);
    return merge(mergeSort($left), mergeSort($right));
}

function merge($left, $right) {
    $result = [];
    $lIndex = $rIndex = 0;
    while ($lIndex < count($left) && $rIndex < count($right)) {
        if ($left[$lIndex] < $right[$rIndex]) {
            $result[] = $left[$lIndex++];
        } else {
            $result[] = $right[$rIndex++];
        }
    }
    while ($lIndex < count($left)) {
        $result[] = $left[$lIndex++];
    }
    while ($rIndex < count($right)) {
        $result[] = $right[$rIndex++];
    }
    return $result;
}

#實戰案例

考慮一個無序的整數陣列

[5 , 2, 8, 3, 1, 9, 4, 7, 6].

使用快排：

$sortedArray = quickSort([5, 2, 8, 3, 1, 9, 4, 7, 6]);
print_r($sortedArray);

輸出：

[1, 2, 3, 4, 5, 6, 7, 8, 9]

使用歸併排序：

$sortedArray = mergeSort([5, 2, 8, 3, 1, 9, 4, 7, 6]);
print_r($sortedArray);

輸出：

[1, 2, 3, 4, 5, 6, 7, 8, 9]

以上是PHP 陣列快排 vs. 歸併排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！