PHP中的數組排序及搜尋演算法

PHP是一種非常流行的程式語言，它支援各種資料類型和演算法，其中數組排序和搜尋演算法是基本且重要的部分。本文將會介紹PHP常用的陣列排序及搜尋演算法，以及它們的應用場景與效率分析。

一、陣列排序

PHP中提供了多種陣列排序的方法，包括冒泡排序、插入排序、選擇排序、快速排序、歸併排序等等。以下是對其中常用的幾種演算法的介紹及範例程式碼：

1. 冒泡排序（Bubble Sort）

冒泡排序是一種簡單卻低效的排序演算法，其基本思想是從數組的第一個元素開始，依序比較相鄰元素的大小，若左邊元素大於右邊元素，則交換它們的位置。這樣一輪比較下來，最大的元素就移到了陣列的末端。接著再從第一個元素開始，重複上述操作，其時間複雜度為O(n^2)。

範例程式碼：

function bubble_sort($arr) {
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) {
        for ($j = 0; $j < $len - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
            }
        }
    }
    return $arr;
}

2. 插入排序（Insertion Sort）

插入排序是一種相對簡單的排序演算法，其基本思想是將一個待排序的資料插入到已經有序的序列中，以達到排序的目的。假設前面的元素已經排序好，從陣列的第二個元素開始向前尋找合適的位置進行插入操作。與冒泡排序類似，其時間複雜度也為O(n^2)。

範例程式碼：

function insertion_sort($arr) {
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        $temp = $arr[$i];
        for ($j = $i - 1; $j >= 0 && $arr[$j] > $temp; $j--) {
            $arr[$j + 1] = $arr[$j];
        }
        $arr[$j + 1] = $temp;
    }
    return $arr;
}

3. 快速排序（Quick Sort）

快速排序是常用的高效排序演算法，其基本想法是選取陣列中任一個元素作為基準值，然後將剩餘的元素分成兩個子序列：左邊的數都比基準值小，右邊的數都比基準值大。接著再對左、右子序列重複以上步驟，直到子序列的長度為1或0。快速排序的時間複雜度為O(n log2 n)，且它是不穩定排序。

範例程式碼：

function quick_sort($arr) {
    $len = count($arr);
    if ($len <= 1) {
        return $arr;
    }
    $pivot_key = $arr[0];
    $left_arr = array();
    $right_arr = array();
    for ($i = 1; $i < $len; $i++) {
        if ($arr[$i] <= $pivot_key) {
            $left_arr[] = $arr[$i];
        } else {
            $right_arr[] = $arr[$i];
        }
    }
    $left_arr = quick_sort($left_arr);
    $right_arr = quick_sort($right_arr);
    return array_merge($left_arr, array($pivot_key), $right_arr);
}

二、陣列搜尋

PHP中的陣列搜尋演算法主要包括線性搜尋、二分搜尋和雜湊搜尋。以下是對其中常用的幾種演算法的介紹及範例程式碼：

1. 線性搜尋（Linear Search）

線性搜尋是一種簡單的查找演算法，其基本想法是從陣列的第一個元素開始，逐一比較元素的值和關鍵字是否相同，若存在則傳回該元素的下標，否則回傳-1。線性搜尋的時間複雜度為O(n)。

範例程式碼：

function linear_search($arr, $key) {
    $len = count($arr);
    for ($i = 0; $i < $len; $i++) {
        if ($arr[$i] == $key) {
            return $i;
        }
    }
    return -1;
}

2. 二分搜尋（Binary Search）

二分搜尋也稱折半查找，其基本想法是將有序數組分成兩部分，每次比較中間元素和關鍵字的大小，若相等則傳回該元素的下標，否則根據大小關係將搜尋範圍縮小一半，直到找出目標元素。二分搜尋的時間複雜度為O(log2 n)。

範例程式碼：

function binary_search($arr, $key) {
    $low = 0;
    $high = count($arr) - 1;
    while ($low <= $high) {
        $mid = floor(($low + $high) / 2);
        if ($arr[$mid] == $key) {
            return $mid;
        } elseif ($arr[$mid] > $key) {
            $high = $mid - 1;
        } else {
            $low = $mid + 1;
        }
    }
    return -1;
}

3. 哈希搜尋（Hash Search）

哈希搜尋是一種利用哈希表的高效查找演算法。其基本概念是將每個元素的關鍵字映射到雜湊表中，透過一個雜湊函數計算出其所在的位置，然後在該位置中尋找所需元素。哈希搜尋的時間複雜度為O(1)，但是需要建構和維護哈希表。

以上就是PHP中常用的陣列排序及搜尋演算法的介紹及範例程式碼，根據實際應用場景和資料規模選擇不同的演算法可以提高程式碼的效率。

以上是PHP中的數組排序及搜尋演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！