PHP 插入排序算法
最后修改于 2025 年 4 月 16 日
基本定义
算法 是一种逐步解决问题或执行计算的程序。在编程中，算法被实现为函数或方法。
排序 是指将数据按特定顺序排列，通常是升序或降序。有效的排序对于优化其他算法（如搜索操作）至关重要。
常见的排序算法包括
- 插入排序
- 快速排序
- 归并排序
- 气泡排序
- 选择排序
- 堆排序
插入排序概述
插入排序每次构建最终排序数组的一个项目。它对于小型数据集或几乎已排序的数据集非常有效。该算法通过将数组划分为已排序和未排序的部分来工作。
时间复杂度：最坏情况 O(n²)，最佳情况 O(n)（已排序）。空间复杂度：O(1)，因为它进行原地排序。
基本插入排序实现
这是 PHP 中针对数值数据的插入排序的基本实现。
basic_insertion_sort.php
<?php
function insertionSort(array &$arr): void {
$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;
}
}
$numbers = [12, 11, 13, 5, 6];
insertionSort($numbers);
print_r($numbers); // Outputs sorted array: [5, 6, 11, 12, 13]
此实现按升序对数组进行排序。该算法选取每个元素并将其插入到已排序部分的正确位置。
对文本数据进行排序
插入排序也可以按字母顺序对字符串进行排序。 这是一个例子。
textual_sort.php
<?php
function insertionSortText(array &$arr): void {
$n = count($arr);
for ($i = 1; $i < $n; $i++) {
$key = $arr[$i];
$j = $i - 1;
while ($j >= 0 && strcmp($arr[$j], $key) > 0) {
$arr[$j + 1] = $arr[$j];
$j--;
}
$arr[$j + 1] = $key;
}
}
$names = ["John", "Alice", "Bob", "Eve", "David"];
insertionSortText($names);
print_r($names); // Outputs: ["Alice", "Bob", "David", "Eve", "John"]
此版本使用 strcmp 比较字符串。该算法与数值版本类似，但比较字符串值。
降序排序
要按降序排序，我们只需反转比较条件。
descending_sort.php
<?php
function insertionSortDesc(array &$arr): void {
$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;
}
}
$numbers = [12, 11, 13, 5, 6];
insertionSortDesc($numbers);
print_r($numbers); // Outputs: [13, 12, 11, 6, 5]
唯一的更改是将比较运算符从 > 更改为 <。 这使得算法按降序排序而不是升序。
通用插入排序函数
我们可以创建一个更灵活的版本，该版本接受比较回调。
generic_insertion_sort.php
<?php
function insertionSortGeneric(array &$arr, callable $compare): void {
$n = count($arr);
for ($i = 1; $i < $n; $i++) {
$key = $arr[$i];
$j = $i - 1;
while ($j >= 0 && $compare($arr[$j], $key) > 0) {
$arr[$j + 1] = $arr[$j];
$j--;
}
$arr[$j + 1] = $key;
}
}
// Ascending sort
$numbers = [12, 11, 13, 5, 6];
insertionSortGeneric($numbers, fn($a, $b) => $a - $b);
print_r($numbers);
// Descending sort
insertionSortGeneric($numbers, fn($a, $b) => $b - $a);
print_r($numbers);
// String sort
$names = ["John", "Alice", "Bob"];
insertionSortGeneric($names, 'strcmp');
print_r($names);
此版本更通用，因为它将比较逻辑委托给回调函数。 相同的函数现在可以处理不同的排序顺序和数据类型。
插入排序与快速排序基准测试
让我们比较插入排序和快速排序，看看性能差异。
sort_benchmark.php
<?php
function quickSort(array &$arr, int $low, int $high): void {
if ($low < $high) {
$pi = partition($arr, $low, $high);
quickSort($arr, $low, $pi - 1);
quickSort($arr, $pi + 1, $high);
}
}
function partition(array &$arr, int $low, int $high): int {
$pivot = $arr[$high];
$i = $low - 1;
for ($j = $low; $j < $high; $j++) {
if ($arr[$j] < $pivot) {
$i++;
[$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]];
}
}
[$arr[$i + 1], $arr[$high]] = [$arr[$high], $arr[$i + 1]];
return $i + 1;
}
function generateRandomArray(int $size): array {
$arr = [];
for ($i = 0; $i < $size; $i++) {
$arr[] = rand(1, 10000);
}
return $arr;
}
$smallArray = generateRandomArray(100);
$mediumArray = generateRandomArray(1000);
$largeArray = generateRandomArray(10000);
// Benchmark insertion sort
$start = microtime(true);
$arr = $smallArray;
insertionSortGeneric($arr, fn($a, $b) => $a - $b);
$time = microtime(true) - $start;
echo "Insertion sort (100): $time seconds\n";
$start = microtime(true);
$arr = $mediumArray;
insertionSortGeneric($arr, fn($a, $b) => $a - $b);
$time = microtime(true) - $start;
echo "Insertion sort (1000): $time seconds\n";
// Benchmark quick sort
$start = microtime(true);
$arr = $smallArray;
quickSort($arr, 0, count($arr) - 1);
$time = microtime(true) - $start;
echo "Quick sort (100): $time seconds\n";
$start = microtime(true);
$arr = $mediumArray;
quickSort($arr, 0, count($arr) - 1);
$time = microtime(true) - $start;
echo "Quick sort (1000): $time seconds\n";
$start = microtime(true);
$arr = $largeArray;
quickSort($arr, 0, count($arr) - 1);
$time = microtime(true) - $start;
echo "Quick sort (10000): $time seconds\n";
预期输出将显示插入排序对于非常小的数组更快，但随着数组大小的增长，它会变得比快速排序慢得多。快速排序的 O(n log n) 平均情况优于插入排序的 O(n²) 对于更大的数据集。
何时使用插入排序
- 小型数据集：对于元素数量 ≤ 10-20 的数组效率很高
- 几乎已排序的数据：在数组基本已排序时表现良好
- 简单的实现：易于理解和实现
- 稳定排序：保持相等元素的相对顺序
来源
本教程涵盖了 PHP 插入排序算法，并提供了数值和文本数据、不同排序顺序和性能比较的示例。
作者
列出 所有 PHP 教程。