PHP中的數組排序及搜尋演算法-php教程-PHP中文網

首頁

後端開發

php教程

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

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Jun 23, 2023 am 09:45 AM

php演算法 php數組排序 php數組搜尋

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

一、陣列排序

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

冒泡排序（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;
}

登入後複製

插入排序（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;
}

登入後複製

快速排序（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中的陣列搜尋演算法主要包括線性搜尋、二分搜尋和雜湊搜尋。以下是對其中常用的幾種演算法的介紹及範例程式碼：

線性搜尋（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;
}

登入後複製

二分搜尋（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;
}

登入後複製