当前位置：首页 > PHP

php算法实现

2026-02-15 02:40:33PHP

PHP 算法实现指南

PHP 作为一种广泛使用的服务器端脚本语言，适用于多种算法实现场景。以下是常见算法在 PHP 中的实现方法。

排序算法

冒泡排序

function bubbleSort($array) {
    $n = count($array);
    for ($i = 0; $i < $n; $i++) {
        for ($j = 0; $j < $n - $i - 1; $j++) {
            if ($array[$j] > $array[$j + 1]) {
                $temp = $array[$j];
                $array[$j] = $array[$j + 1];
                $array[$j + 1] = $temp;
            }
        }
    }
    return $array;
}

快速排序

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

搜索算法

二分查找

function binarySearch($array, $target) {
    $low = 0;
    $high = count($array) - 1;
    while ($low <= $high) {
        $mid = floor(($low + $high) / 2);
        if ($array[$mid] == $target) {
            return $mid;
        }
        if ($array[$mid] < $target) {
            $low = $mid + 1;
        } else {
            $high = $mid - 1;
        }
    }
    return -1;
}

图算法

Dijkstra 最短路径算法

function dijkstra($graph, $start) {
    $distances = [];
    $visited = [];
    $queue = new SplPriorityQueue();

    foreach ($graph as $vertex => $adj) {
        $distances[$vertex] = INF;
        $visited[$vertex] = false;
    }

    $distances[$start] = 0;
    $queue->insert($start, 0);

    while (!$queue->isEmpty()) {
        $u = $queue->extract();
        if ($visited[$u]) continue;
        $visited[$u] = true;

        foreach ($graph[$u] as $v => $weight) {
            $alt = $distances[$u] + $weight;
            if ($alt < $distances[$v]) {
                $distances[$v] = $alt;
                $queue->insert($v, -$alt);
            }
        }
    }
    return $distances;
}

动态规划

斐波那契数列

function fibonacci($n) {
    $dp = [];
    $dp[0] = 0;
    $dp[1] = 1;
    for ($i = 2; $i <= $n; $i++) {
        $dp[$i] = $dp[$i - 1] + $dp[$i - 2];
    }
    return $dp[$n];
}

字符串算法

KMP 字符串匹配

function computeLPSArray($pattern) {
    $lps = [0];
    $len = 0;
    $i = 1;
    $M = strlen($pattern);

    while ($i < $M) {
        if ($pattern[$i] == $pattern[$len]) {
            $len++;
            $lps[$i] = $len;
            $i++;
        } else {
            if ($len != 0) {
                $len = $lps[$len - 1];
            } else {
                $lps[$i] = 0;
                $i++;
            }
        }
    }
    return $lps;
}

function KMPSearch($text, $pattern) {
    $N = strlen($text);
    $M = strlen($pattern);
    $lps = computeLPSArray($pattern);
    $i = $j = 0;

    while ($i < $N) {
        if ($pattern[$j] == $text[$i]) {
            $i++;
            $j++;
        }
        if ($j == $M) {
            return $i - $j;
            $j = $lps[$j - 1];
        } elseif ($i < $N && $pattern[$j] != $text[$i]) {
            if ($j != 0) {
                $j = $lps[$j - 1];
            } else {
                $i++;
            }
        }
    }
    return -1;
}