PHP 实现五种经典排序算法详解与示例
编辑：本站更新：2024-04-19 08:36:25人气：3561
在计算机科学领域，排序算法是编程中最基础且重要的部分之一。PHP作为一种广泛应用的服务器端脚本语言，在处理数组和数据结构时自然也离不开各种高效稳定的排序方法实现。接下来我们将深入探讨如何用PHP来实现在程序设计中常见的五种经典排序算法：冒泡排序、选择排序、插入排序、快速排序以及归并排序，并通过具体的代码实例加以演示。
1. **冒泡排序(Bubble Sort)**
冒泡排序是一种简单直观的比较型排序算法，它重复地遍历待排元素列表，一次比较两个相邻项，如果顺序错误则交换它们的位置，直到没有更多的需要交换的情况出现为止。
function bubbleSort($array) {
$length = count($array);
for ($i=0; $i<$length-1 ;$i++) {
// 每轮循环都会至少有一个数被放到正确位置上
for ($j=0;$j<$length-$i-1;$j++){
if ($array[$j] > $array[$j+1]){
list($array[$j], $array[$j+1]) = array($array[$j+1],$array[$j]); // swap elements
}
}
}
return $array;
}
$array = [34,27,89,65,12];
print_r(bubbleSort($array));
2. **选择排序(Selection Sort)**
在每一轮迭代过程中找到剩余未排序序列中的最小（或最大）值，将其放在已排序区间的末尾。
function selectionSort(&$arr){
$len = count($arr);
for ($i = 0; $i < $len - 1; $i++){
$minIndex = $i;
for ($j = $i + 1; $j < $len; $j++)
if ($arr[$j] < $arr[$minIndex])
$minIndex = $j;
// Swap the found minimum element with the first element of 'unsorted part'
$temp = $arr[$i];
$arr[$i] = $arr[$minIndex];
$arr[$minIndex] = $temp;
}
return $arr;
}
$arr = [9,5,2,7,1,6];
print_r(selectionSort($arr));
3. **插入排序(Insertion Sort)**
插入排序的工作原理就像是我们打扑克牌一样，每次从手中抽取一张卡片并将之插到正确的有序序列里。
function insertionSort(array &$items): void{
$count = count($items);
for ($outer = 1; $outer <= $count - 1; ++$outer)
{
$valueToOrder = $items[$outer];
$inner = $outer;
while (
$inner !== 0 &&
$items[ $inner - 1 ] > $valueToOrder
)
{
$items[$inner] = $items[--$inner];
}
$items[$inner] = $valueToOrder;
}
}
/items = [5,3,2,8,1];
insertionSort($items);
echo implode(', ', $items);
4. **快速排序(Quick Sort)**
快速排序采用分治策略，首先选取一个基准点将整个序列划分为两半，然后对每一半再进行相同的操作直至每个子区间只剩下一个或者为空。
function quicksort($array)
{
if(count($array)<2)
return $array;
else
{
$left=$right=array();
reset($array);
$pivot=key($array);
foreach($array as $k => $v)
{
if($k==$pivot) continue;
(strcmp($v,$array[$pivot])<0)?$left[]=$v:$right[]=$v;
}
return array_merge(quicksort($left),array($array[$pivot]),quicksort($right));
}
}
$array=[3,6,8,10,1,2,1];
print_r(quicksort($array));
5. **归并排序(Merge Sort)**
归并排序也是运用了“分而治之”的思想，但不同于快排的是其始终保证分解出的小问题是相互独立的，最后使用合并操作完成整体排序任务。
function merge_sort (&$input_array)
{
if<count($input_array)>1):
$midpoint = floor(count($input_array)/2);
$left_half = array_slice($input_array, 0, $midpoint );
$right_half = array_slice($input_array, $midpoint );
merge_sort($left_half);
merge_sort($right_half);
$merge_count = count($left_half);
$lpos = 0;
$rpos = 0;
for ($idx = 0; $idx < count($input_array); $idx++ )
{
if ($lpos == $merge_count ):
$input_array [$idx] = $right_half[$rpos++];
elseif ($rpos==count($right_half)):
$input_array[$idx]=$left_half[$lpos++];
elseif ($left_half[$lpos]<=$right_half[$rpos]):
$input_array[$idx]=@$left_half[$lpos++];
else:
$input_array[$idx]=@$right_half[$rpos++];
endif ;
}
endif ;
}
$input_array = Array(3,2,6,1,-1,9,5);
merge_sort($input_array);
print("Sorted ARRAY:");
foreach ($input_array as $key=>$val){ echo "$val ";};
以上就是利用PHP实现五大经典的排序算法及其详细解释及示例。理解这些基本算法不仅有助于提升我们在实际开发过程中的问题解决能力，也能加深对于时间复杂度和空间复杂度等核心概念的理解，从而更好地优化我们的编码实践。
1. **冒泡排序(Bubble Sort)**
冒泡排序是一种简单直观的比较型排序算法，它重复地遍历待排元素列表，一次比较两个相邻项，如果顺序错误则交换它们的位置，直到没有更多的需要交换的情况出现为止。
php
function bubbleSort($array) {
$length = count($array);
for ($i=0; $i<$length-1 ;$i++) {
// 每轮循环都会至少有一个数被放到正确位置上
for ($j=0;$j<$length-$i-1;$j++){
if ($array[$j] > $array[$j+1]){
list($array[$j], $array[$j+1]) = array($array[$j+1],$array[$j]); // swap elements
}
}
}
return $array;
}
$array = [34,27,89,65,12];
print_r(bubbleSort($array));
2. **选择排序(Selection Sort)**
在每一轮迭代过程中找到剩余未排序序列中的最小（或最大）值，将其放在已排序区间的末尾。
php
function selectionSort(&$arr){
$len = count($arr);
for ($i = 0; $i < $len - 1; $i++){
$minIndex = $i;
for ($j = $i + 1; $j < $len; $j++)
if ($arr[$j] < $arr[$minIndex])
$minIndex = $j;
// Swap the found minimum element with the first element of 'unsorted part'
$temp = $arr[$i];
$arr[$i] = $arr[$minIndex];
$arr[$minIndex] = $temp;
}
return $arr;
}
$arr = [9,5,2,7,1,6];
print_r(selectionSort($arr));
3. **插入排序(Insertion Sort)**
插入排序的工作原理就像是我们打扑克牌一样，每次从手中抽取一张卡片并将之插到正确的有序序列里。
php
function insertionSort(array &$items): void{
$count = count($items);
for ($outer = 1; $outer <= $count - 1; ++$outer)
{
$valueToOrder = $items[$outer];
$inner = $outer;
while (
$inner !== 0 &&
$items[ $inner - 1 ] > $valueToOrder
)
{
$items[$inner] = $items[--$inner];
}
$items[$inner] = $valueToOrder;
}
}
/items = [5,3,2,8,1];
insertionSort($items);
echo implode(', ', $items);
4. **快速排序(Quick Sort)**
快速排序采用分治策略，首先选取一个基准点将整个序列划分为两半，然后对每一半再进行相同的操作直至每个子区间只剩下一个或者为空。
php
function quicksort($array)
{
if(count($array)<2)
return $array;
else
{
$left=$right=array();
reset($array);
$pivot=key($array);
foreach($array as $k => $v)
{
if($k==$pivot) continue;
(strcmp($v,$array[$pivot])<0)?$left[]=$v:$right[]=$v;
}
return array_merge(quicksort($left),array($array[$pivot]),quicksort($right));
}
}
$array=[3,6,8,10,1,2,1];
print_r(quicksort($array));
5. **归并排序(Merge Sort)**
归并排序也是运用了“分而治之”的思想，但不同于快排的是其始终保证分解出的小问题是相互独立的，最后使用合并操作完成整体排序任务。
php
function merge_sort (&$input_array)
{
if<count($input_array)>1):
$midpoint = floor(count($input_array)/2);
$left_half = array_slice($input_array, 0, $midpoint );
$right_half = array_slice($input_array, $midpoint );
merge_sort($left_half);
merge_sort($right_half);
$merge_count = count($left_half);
$lpos = 0;
$rpos = 0;
for ($idx = 0; $idx < count($input_array); $idx++ )
{
if ($lpos == $merge_count ):
$input_array [$idx] = $right_half[$rpos++];
elseif ($rpos==count($right_half)):
$input_array[$idx]=$left_half[$lpos++];
elseif ($left_half[$lpos]<=$right_half[$rpos]):
$input_array[$idx]=@$left_half[$lpos++];
else:
$input_array[$idx]=@$right_half[$rpos++];
endif ;
}
endif ;
}
$input_array = Array(3,2,6,1,-1,9,5);
merge_sort($input_array);
print("Sorted ARRAY:");
foreach ($input_array as $key=>$val){ echo "$val ";};
以上就是利用PHP实现五大经典的排序算法及其详细解释及示例。理解这些基本算法不仅有助于提升我们在实际开发过程中的问题解决能力，也能加深对于时间复杂度和空间复杂度等核心概念的理解，从而更好地优化我们的编码实践。
www.php580.com PHP工作室 - 全面的PHP教程、实例、框架与实战资源
PHP学习网是专注于PHP技术学习的一站式在线平台，提供丰富全面的PHP教程、深入浅出的实例解析、主流PHP框架详解及实战应用，并涵盖PHP面试指南、最新资讯和活跃的PHP开发者社区。无论您是初学者还是进阶者，这里都有助于提升您的PHP编程技能。
转载内容版权归作者及来源网站所有，本站原创内容转载请注明来源。