php实现排序算法
PHP实现冒泡排序
冒泡排序通过重复遍历数组，比较相邻元素并交换位置，将较大元素逐渐“冒泡”到数组末尾。
function bubbleSort($arr) {
$n = count($arr);
for ($i = 0; $i < $n - 1; $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;
}
}
}
return $arr;
}PHP实现快速排序
快速排序通过选择一个基准元素，将数组分为两部分，递归排序子数组。
function quickSort($arr) {
if (count($arr) <= 1) {
return $arr;
}
$pivot = $arr[0];
$left = $right = [];
for ($i = 1; $i < count($arr); $i++) {
if ($arr[$i] < $pivot) {
$left[] = $arr[$i];
} else {
$right[] = $arr[$i];
}
}
return array_merge(quickSort($left), [$pivot], quickSort($right));
}PHP实现选择排序
选择排序每次从未排序部分选择最小元素，放到已排序部分的末尾。
function selectionSort($arr) {
$n = count($arr);
for ($i = 0; $i < $n - 1; $i++) {
$minIndex = $i;
for ($j = $i + 1; $j < $n; $j++) {
if ($arr[$j] < $arr[$minIndex]) {
$minIndex = $j;
}
}
// 交换最小元素到当前位置
$temp = $arr[$i];
$arr[$i] = $arr[$minIndex];
$arr[$minIndex] = $temp;
}
return $arr;
}PHP实现插入排序
插入排序通过构建有序序列，逐个将未排序元素插入到正确位置。
function insertionSort($arr) {
$n = count($arr);
for ($i = 1; $i < $n; $i++) {
$key = $arr[$i];
$j = $i - 1;
while ($j >= 0 && $arr[$j] > $key) {
$arr[$j + 1] = $arr[$j];
$j--;
}
$arr[$j + 1] = $key;
}
return $arr;
}PHP实现归并排序
归并排序采用分治法，将数组分成两半递归排序，再合并两个有序子数组。
function mergeSort($arr) {
if (count($arr) <= 1) {
return $arr;
}
$mid = (int)(count($arr) / 2);
$left = array_slice($arr, 0, $mid);
$right = array_slice($arr, $mid);
return merge(mergeSort($left), mergeSort($right));
}
function merge($left, $right) {
$result = [];
while (count($left) > 0 && count($right) > 0) {
if ($left[0] <= $right[0]) {
$result[] = array_shift($left);
} else {
$result[] = array_shift($right);
}
}
return array_merge($result, $left, $right);
}注意事项
- 时间复杂度：冒泡和选择排序为 $O(n^2)$，快速和归并排序为 $O(n \log n)$，插入排序最坏情况为 $O(n^2)$。
- 对于小规模数据，插入排序可能比快速排序更快。
- PHP内置函数
sort()使用快速排序实现，优先考虑内置函数。
