PHP：常用算法

陈一男学习网站[ ChenYinan.com ] - CCF - NOI - 菜鸟教程 - 编程题库 - C++语言 - API

在 PHP 中，有一些常用的算法，以下是对它们的介绍：

一、排序算法

1. 冒泡排序（Bubble Sort）：

原理：重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。

示例代码：

function bubbleSort($array) {

$n = count($array);

for ($i = 0; $i < $n - 1; $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;

}

2. 快速排序（Quick Sort）：

原理：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

示例代码：

function quickSort($array) {

if (count($array) <= 1) {

return $array;

}

$pivot = $array[0];

$left = $right = array();

for ($i = 1; $i < count($array); $i++) {

if ($array[$i] < $pivot) {

$left[] = $array[$i];

} else {

$right[] = $array[$i];

}

}

return array_merge(quickSort($left), array($pivot), quickSort($right));

}

二、查找算法

1. 顺序查找（Sequential Search）：

原理：从数组的第一个元素开始，逐个与要查找的关键字进行比较，直到找到为止。

示例代码：

function sequentialSearch($array, $target) {

for ($i = 0; $i < count($array); $i++) {

if ($array[$i] === $target) {

return $i;

}

}

return -1;

}

2. 二分查找（Binary Search）：

原理：对于已排序的数组，每次取中间元素与要查找的关键字进行比较，如果相等则返回中间元素的索引；如果关键字小于中间元素，则在左半部分继续查找；如果关键字大于中间元素，则在右半部分继续查找。

示例代码：

function binarySearch($array, $target) {

$low = 0;

$high = count($array) - 1;

while ($low <= $high) {

$mid = floor(($low + $high) / 2);

if ($array[$mid] === $target) {

return $mid;

} elseif ($array[$mid] < $target) {

$low = $mid + 1;

} else {

$high = $mid - 1;

}

}

return -1;

}

三、字符串处理算法

1. 字符串匹配（String Matching）：

例如使用朴素字符串匹配算法，在一个字符串中查找另一个字符串的出现位置。

原理：逐个字符地比较主串和模式串，如果匹配失败，则主串的指针向后移动一位，模式串的指针回到开头重新开始比较。

示例代码：

function naiveStringSearch($haystack, $needle) {

$m = strlen($haystack);

$n = strlen($needle);

for ($i = 0; $i <= $m - $n; $i++) {

$j = 0;

while ($j < $n && $haystack[$i + $j] === $needle[$j]) {

$j++;

}

if ($j === $n) {

return $i;

}

}

return -1;

}

四、图算法

1. 广度优先搜索（Breadth-First Search，BFS）：

原理：从图的某一顶点出发，首先依次访问该顶点的所有邻接顶点，然后再按这些顶点被访问的先后次序依次访问它们的邻接顶点，直至图中所有和该顶点有路径相通的顶点都被访问到为止。

示例代码（假设使用邻接表表示图）：

function bfs($graph, $start) {

$visited = array_fill(0, count($graph), false);

$queue = new SplQueue();

$queue->enqueue($start);

$visited[$start] = true;

while (!$queue->isEmpty()) {

$vertex = $queue->dequeue();

echo $vertex. " ";

foreach ($graph[$vertex] as $neighbor) {

if (!$visited[$neighbor]) {

$queue->enqueue($neighbor);

$visited[$neighbor] = true;

}

}

}

}

这些只是 PHP 中一些常用的算法，根据不同的需求，可以选择合适的算法来解决问题。在实际应用中，还可以结合数据结构和其他技术来提高算法的效率和性能。

PHP编程语言基础