PHP常見基礎算法實例分析

PHP常見基礎算法實例分析

在編程中，算法是解決問題的核心。無論是簡單的排序還是復雜的搜索，算法都扮演著至關重要的角色。PHP作為一種廣泛使用的服務器端腳本語言，雖然主要用于Web開發，但在處理數據時，掌握一些基礎算法仍然是非常有用的。本文將介紹幾種常見的PHP基礎算法，并通過實例進行分析。

1. 冒泡排序（Bubble Sort）

冒泡排序是一種簡單的排序算法，它重復地遍歷要排序的列表，比較相鄰的元素并交換它們的位置，直到整個列表排序完成。

實例代碼

function bubbleSort($arr) {
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        for ($j = 0; $j < $n - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                // 交換位置
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
            }
        }
    }
    return $arr;
}

$arr = [64, 34, 25, 12, 22, 11, 90];
$sortedArr = bubbleSort($arr);
print_r($sortedArr);

分析

• 時間復雜度：O(n^2)，其中n是數組的長度。
• 空間復雜度：O(1)，因為只使用了常數級別的額外空間。

2. 選擇排序（Selection Sort）

選擇排序是一種簡單直觀的排序算法。它的工作原理是每次從未排序的部分中選擇最?。ɑ蜃畲螅┑脑?，放到已排序部分的末尾。

實例代碼

function selectionSort($arr) {
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        $minIndex = $i;
        for ($j = $i + 1; $j < $n; $j++) {
            if ($arr[$j] < $arr[$minIndex]) {
                $minIndex = $j;
            }
        }
        // 交換位置
        $temp = $arr[$i];
        $arr[$i] = $arr[$minIndex];
        $arr[$minIndex] = $temp;
    }
    return $arr;
}

$arr = [64, 25, 12, 22, 11];
$sortedArr = selectionSort($arr);
print_r($sortedArr);

分析

• 時間復雜度：O(n^2)，其中n是數組的長度。
• 空間復雜度：O(1)，因為只使用了常數級別的額外空間。

3. 插入排序（Insertion Sort）

插入排序是一種簡單直觀的排序算法，它的工作原理是通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。

實例代碼

function insertionSort($arr) {
    $n = count($arr);
    for ($i = 1; $i < $n; $i++) {
        $key = $arr[$i];
        $j = $i - 1;
        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }
        $arr[$j + 1] = $key;
    }
    return $arr;
}

$arr = [12, 11, 13, 5, 6];
$sortedArr = insertionSort($arr);
print_r($sortedArr);

分析

• 時間復雜度：O(n^2)，其中n是數組的長度。
• 空間復雜度：O(1)，因為只使用了常數級別的額外空間。

4. 二分查找（Binary Search）

二分查找是一種高效的查找算法，適用于已排序的數組。它的工作原理是通過將查找范圍逐步縮小一半來查找目標元素。

實例代碼

function binarySearch($arr, $target) {
    $left = 0;
    $right = count($arr) - 1;
    while ($left <= $right) {
        $mid = $left + intval(($right - $left) / 2);
        if ($arr[$mid] == $target) {
            return $mid;
        } elseif ($arr[$mid] < $target) {
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }
    return -1; // 未找到
}

$arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
$target = 5;
$index = binarySearch($arr, $target);
echo "目標元素在數組中的索引是: " . $index;

分析

• 時間復雜度：O(log n)，其中n是數組的長度。
• 空間復雜度：O(1)，因為只使用了常數級別的額外空間。

5. 快速排序（Quick Sort）

快速排序是一種高效的排序算法，采用分治法策略。它的工作原理是選擇一個基準元素，將數組分為兩部分，一部分小于基準元素，另一部分大于基準元素，然后遞歸地對這兩部分進行排序。

實例代碼

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

$arr = [10, 80, 30, 90, 40, 50, 70];
$sortedArr = quickSort($arr);
print_r($sortedArr);

分析

• 時間復雜度：平均情況下為O(n log n)，最壞情況下為O(n^2)。
• 空間復雜度：O(log n)，因為遞歸調用棧的深度。

總結

本文介紹了PHP中幾種常見的基礎算法，包括冒泡排序、選擇排序、插入排序、二分查找和快速排序。這些算法雖然簡單，但在實際開發中非常有用。通過理解和掌握這些基礎算法，可以更好地處理數據，提高代碼的效率和質量。