排序算法 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;
}选择排序
每次选择最小元素放到已排序序列末尾：
function selectionSort($arr) {
$n = count($arr);
for ($i = 0; $i < $n - 1; $i++) {
$minIdx = $i;
for ($j = $i + 1; $j < $n; $j++) {
if ($arr[$j] < $arr[$minIdx]) {
$minIdx = $j;
}
}
if ($minIdx != $i) {
$temp = $arr[$i];
$arr[$i] = $arr[$minIdx];
$arr[$minIdx] = $temp;
}
}
return $arr;
}插入排序
构建有序序列，逐个将未排序元素插入合适位置：
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;
}快速排序
分治法策略，选取基准元素分割数组：
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));
}归并排序
分治法将数组拆分为最小单元后合并排序：
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²)，适合小数据集
- 插入排序：时间复杂度O(n²)，对近乎有序数据效率高
- 快速排序：平均时间复杂度O(n log n)，需注意最坏情况
- 归并排序：稳定O(n log n)，但需要额外空间
实际使用时可根据数据特性和规模选择合适的算法。PHP内置的sort()函数通常采用优化后的快速排序实现。
