PHP 选择排序算法
最后修改于 2025 年 4 月 16 日
基本定义
一个 算法 是一个解决问题的逐步过程。在编程中，算法被实现为函数或方法。
排序 意味着将数据按特定顺序排列，通常是升序或降序。有效的排序对于优化数据访问至关重要。
常见的排序算法包括
- 选择排序
- 气泡排序
- 插入排序
- 归并排序
- 快速排序
- 堆排序
选择排序算法
选择排序通过反复找到未排序部分中的最小（或最大）元素并将其放在开头来工作。它具有 O(n²) 的时间复杂度，这使得它对于大型数据集来说效率较低。
选择排序实现
这是一个用 PHP 实现的选择排序的基本实现，用于数字数据
selection_sort.php
<?php
function selectionSort(array $arr): array {
$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;
}
}
if ($minIndex != $i) {
// Swap elements
$temp = $arr[$i];
$arr[$i] = $arr[$minIndex];
$arr[$minIndex] = $temp;
}
}
return $arr;
}
$numbers = [64, 25, 12, 22, 11];
$sorted = selectionSort($numbers);
print_r($sorted); // Outputs: [11, 12, 22, 25, 64]
此实现按升序对数字进行排序。外循环跟踪已排序的部分，而内循环查找下一个最小的元素。
降序排序
要按降序排序，我们修改比较以找到最大值
selection_sort_desc.php
<?php
function selectionSortDesc(array $arr): array {
$n = count($arr);
for ($i = 0; $i < $n - 1; $i++) {
$maxIndex = $i;
for ($j = $i + 1; $j < $n; $j++) {
if ($arr[$j] > $arr[$maxIndex]) {
$maxIndex = $j;
}
}
if ($maxIndex != $i) {
// Swap elements
$temp = $arr[$i];
$arr[$i] = $arr[$maxIndex];
$arr[$maxIndex] = $temp;
}
}
return $arr;
}
$numbers = [64, 25, 12, 22, 11];
$sorted = selectionSortDesc($numbers);
print_r($sorted); // Outputs: [64, 25, 22, 12, 11]
唯一的改变是将比较运算符从 < 改为 > 以找到最大值而不是最小值。
对文本数据进行排序
选择排序也可以按字母顺序对字符串进行排序
selection_sort_strings.php
<?php
function selectionSortStrings(array $arr): array {
$n = count($arr);
for ($i = 0; $i < $n - 1; $i++) {
$minIndex = $i;
for ($j = $i + 1; $j < $n; $j++) {
if (strcmp($arr[$j], $arr[$minIndex]) < 0) {
$minIndex = $j;
}
}
if ($minIndex != $i) {
$temp = $arr[$i];
$arr[$i] = $arr[$minIndex];
$arr[$minIndex] = $temp;
}
}
return $arr;
}
$names = ["John", "Alice", "Bob", "Eve", "David"];
$sorted = selectionSortStrings($names);
print_r($sorted); // Outputs: ["Alice", "Bob", "David", "Eve", "John"]
我们使用 strcmp 进行字符串比较。如果第一个字符串小于第二个字符串，则它返回一个小于 0 的值。
通用选择排序
我们可以创建一个更通用的版本，该版本接受一个比较回调
generic_selection_sort.php
<?php
function selectionSortGeneric(array $arr, callable $compare): array {
$n = count($arr);
for ($i = 0; $i < $n - 1; $i++) {
$selectedIndex = $i;
for ($j = $i + 1; $j < $n; $j++) {
if ($compare($arr[$j], $arr[$selectedIndex])) {
$selectedIndex = $j;
}
}
if ($selectedIndex != $i) {
$temp = $arr[$i];
$arr[$i] = $arr[$selectedIndex];
$arr[$selectedIndex] = $temp;
}
}
return $arr;
}
// Sort numbers ascending
$numbers = [64, 25, 12, 22, 11];
$sortedAsc = selectionSortGeneric($numbers, fn($a, $b) => $a < $b);
print_r($sortedAsc);
// Sort strings descending
$names = ["John", "Alice", "Bob", "Eve", "David"];
$sortedDesc = selectionSortGeneric($names, fn($a, $b) => strcmp($a, $b) > 0);
print_r($sortedDesc);
此版本更灵活，因为它将比较逻辑委托给调用者。如果第一个参数应该在排序顺序中位于第二个参数之前，则回调应返回 true。
选择排序 vs 快速排序
让我们将选择排序与更有效的快速排序算法进行比较
sort_benchmark.php
<?php
function quickSort(array $arr): array {
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));
}
// Generate large array
$largeArray = range(1, 10000);
shuffle($largeArray);
// Benchmark selection sort
$start = microtime(true);
selectionSortGeneric($largeArray, fn($a, $b) => $a < $b);
$selectionTime = microtime(true) - $start;
// Benchmark quick sort
$start = microtime(true);
quickSort($largeArray);
$quickTime = microtime(true) - $start;
echo "Selection Sort: " . number_format($selectionTime, 4) . " seconds\n";
echo "Quick Sort: " . number_format($quickTime, 4) . " seconds\n";
在具有 10,000 个元素的典型机器上，您将看到类似的结果
Selection Sort: 2.3456 seconds Quick Sort: 0.0123 seconds
快速排序对于大型数据集明显更快，因为它具有 O(n log n) 的平均时间复杂度，而选择排序的平均时间复杂度为 O(n²)。但是，对于小型数据集，选择排序可能更容易实现和理解。
何时使用选择排序
- 小型数据集： 当 n 较小时，开销影响较小。
- 内存限制： 这是一个原地排序，空间复杂度为 O(1)。
- 简单实现： 适用于教育目的。
- 很少需要交换： 总共只需要 O(n) 次交换。
来源
本教程涵盖了 PHP 中的选择排序算法，并提供了数字和文本数据的示例，包括性能比较。
作者
列出 所有 PHP 教程。