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]) {
$temp = $array[$j];
$array[$j] = $array[$j + 1];
$array[$j + 1] = $temp;
}
}
}
return $array;
}选择排序
选择排序每次遍历找到最小元素，与当前未排序部分的起始位置交换。
function selectionSort($array) {
$length = count($array);
for ($i = 0; $i < $length - 1; $i++) {
$minIndex = $i;
for ($j = $i + 1; $j < $length; $j++) {
if ($array[$j] < $array[$minIndex]) {
$minIndex = $j;
}
}
if ($minIndex != $i) {
$temp = $array[$i];
$array[$i] = $array[$minIndex];
$array[$minIndex] = $temp;
}
}
return $array;
}插入排序
插入排序将未排序元素逐个插入已排序部分的正确位置。
function insertionSort($array) {
$length = count($array);
for ($i = 1; $i < $length; $i++) {
$key = $array[$i];
$j = $i - 1;
while ($j >= 0 && $array[$j] > $key) {
$array[$j + 1] = $array[$j];
$j--;
}
$array[$j + 1] = $key;
}
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 mergeSort($array) {
if (count($array) <= 1) {
return $array;
}
$mid = intdiv(count($array), 2);
$left = mergeSort(array_slice($array, 0, $mid));
$right = mergeSort(array_slice($array, $mid));
return merge($left, $right);
}
function merge($left, $right) {
$result = [];
while (!empty($left) && !empty($right)) {
if ($left[0] < $right[0]) {
$result[] = array_shift($left);
} else {
$result[] = array_shift($right);
}
}
return array_merge($result, $left, $right);
}注意事项
- 快速排序和归并排序适合大数据集，时间复杂度为 O(n log n)。
- 冒泡排序和插入排序在小数据集上效率尚可，但时间复杂度为 O(n²)。
- 实际开发中可优先使用 PHP 内置函数
sort()、asort()等，基于优化算法实现。
