php实现常见算法
PHP 中常见算法的实现
引言
算法在计算机科学中至关重要，它们提供了解决复杂问题的系统而有效的方法。PHP 是一门流行的编程语言，由于其广泛的库和灵活的语法，使其成为实现算法的理想选择。本文将介绍 PHP 中一些最常见的算法及其实现。
1. 排序算法
冒泡排序
php
function bubbleSort(array &$arr) {
$n = count($arr);
for ($i = 0; $i < $n; $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;
}
}
}
}
快速排序
php
function quickSort(array &$arr, $low, $high) {
if ($low < $high) {
$pivot = partition($arr, $low, $high);
quickSort($arr, $low, $pivot - 1);
quickSort($arr, $pivot + 1, $high);
}
}
function partition(array &$arr, $low, $high) {
$pivot = $arr[$high];
$i = $low - 1;
for ($j = $low; $j < $high; $j++) {
if ($arr[$j] < $pivot) {
$i++;
$temp = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $temp;
}
}
$temp = $arr[$i + 1];
$arr[$i + 1] = $arr[$high];
$arr[$high] = $temp;
return $i + 1;
}
2. 搜索算法
线性搜索
php
function linearSearch(array $arr, $key) {
$n = count($arr);
for ($i = 0; $i < $n; $i++) {
if ($arr[$i] == $key) {
return $i;
}
}
return -1;
}
二分搜索
php
function binarySearch(array $arr, $key, $low, $high) {
if ($low > $high) {
return -1;
}
$mid = floor(($low + $high) / 2);
if ($arr[$mid] == $key) {
return $mid;
} elseif ($arr[$mid] < $key) {
return binarySearch($arr, $key, $mid + 1, $high);
} else {
return binarySearch($arr, $key, $low, $mid - 1);
}
}
3. 递归算法
阶乘
php
function factorial($n) {
if ($n <= 1) {
return 1;
} else {
return $n * factorial($n - 1);
}
}
斐波那契数列
php
function fibonacci($n) {
if ($n <= 1) {
return $n;
} else {
return fibonacci($n - 1) + fibonacci($n - 2);
}
}
4. 贪婪算法
最短路径
php
function shortestPath(array $graph, $start, $end) {
$dist = array_fill_keys(array_keys($graph), PHP_INT_MAX);
$dist[$start] = 0;
$prev = array_fill_keys(array_keys($graph), -1);
$pq = new SplPriorityQueue();
$pq->insert($start, 0);
while (!$pq->isEmpty()) {
$u = $pq->extract();
if ($u == $end) {
break;
}
foreach ($graph[$u] as $v => $weight) {
$alt = $dist[$u] + $weight;
if ($alt < $dist[$v]) {
$dist[$v] = $alt;
$prev[$v] = $u;
$pq->insert($v, $alt);
}
}
}
$path = array();
$curr = $end;
while ($curr != -1) {
$path[] = $curr;
$curr = $prev[$curr];
}
return $path;
}
5. 动态规划算法
最长公共子序列
php
function lcs(string $str1, string $str2) {
$m = strlen($str1);
$n = strlen($str2);
$dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
for ($i = 1; $i <= $m; $i++) {
for ($j = 1; $j <= $n; $j++) {
if ($str1[$i - 1] == $str2[$j - 1]) {
$dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
} else {
$dp[$i][$j] = max($dp[$i - 1][$j], $dp[$i][$j - 1]);
}
}
}
$lcs = "";
$i = $m;
$j = $n;
while ($i > 0 && $j > 0) {
if ($str1[$i - 1] == $str2[$j - 1]) {
$lcs = $str1[$i - 1] . $lcs;
$i--;
$j--;
} else {
if ($dp[$i - 1][$j] > $dp[$i][$j - 1]) {
$i--;
} else {
$j--;
}
}
}
return $lcs;
}
结论
PHP 提供了实现广泛算法的强大功能。本文中介绍的算法只是众多实用算法中的一小部分，它们可以应用于各种问题域。通过利用 PHP 的库和语法灵活性，开发者可以高效且有效地解决复杂的问题，并创建健壮的应用程序。
- 上一篇:php实现增删改查管理功能
- 下一篇:php实现常见算法
