PHP Shell 排序算法
最后修改于 2025 年 4 月 16 日
基本定义
算法 是一种逐步解决问题或执行计算的程序。在编程中，算法被实现为函数或方法。
排序 是指将数据按特定顺序排列，通常是升序或降序。有效的排序对于优化其他算法（如搜索操作）至关重要。
常见的排序算法包括
- 气泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序
- 堆排序
- Shell Sort（希尔排序）
Shell 排序概述
Shell 排序是插入排序的一种优化，它允许交换相隔较远的项。它的工作原理是按特定的间隔对元素进行排序，然后减小间隔，直到间隔变为 1。
该算法由 Donald Shell 于 1959 年发明。它的时间复杂度根据使用的间隔序列而变化，通常在 O(n) 和 O(n²) 之间。
Shell 排序实现
这是一个 PHP 中对数字数据的 Shell 排序的基本实现
shell_sort.php
<?php
function shellSort(array $arr): array {
$n = count($arr);
$gap = floor($n / 2);
while ($gap > 0) {
for ($i = $gap; $i < $n; $i++) {
$temp = $arr[$i];
$j = $i;
while ($j >= $gap && $arr[$j - $gap] > $temp) {
$arr[$j] = $arr[$j - $gap];
$j -= $gap;
}
$arr[$j] = $temp;
}
$gap = floor($gap / 2);
}
return $arr;
}
$numbers = [12, 34, 54, 2, 3];
$sorted = shellSort($numbers);
print_r($sorted);
此实现将数字按升序排序。间隔从数组长度的一半开始，每次迭代减半，直到达到 0。
对文本数据进行排序
Shell 排序也可以按字母顺序对字符串进行排序。 这是一个例子
shell_sort_strings.php
<?php
function shellSortStrings(array $arr): array {
$n = count($arr);
$gap = floor($n / 2);
while ($gap > 0) {
for ($i = $gap; $i < $n; $i++) {
$temp = $arr[$i];
$j = $i;
while ($j >= $gap && strcmp($arr[$j - $gap], $temp) > 0) {
$arr[$j] = $arr[$j - $gap];
$j -= $gap;
}
$arr[$j] = $temp;
}
$gap = floor($gap / 2);
}
return $arr;
}
$names = ["apple", "orange", "banana", "pear"];
$sortedNames = shellSortStrings($names);
print_r($sortedNames);
此版本使用 strcmp 比较字符串。 它将数组按升序字母顺序排序。
降序排序
要按降序排序，我们只需反转比较条件
shell_sort_desc.php
<?php
function shellSortDesc(array $arr): array {
$n = count($arr);
$gap = floor($n / 2);
while ($gap > 0) {
for ($i = $gap; $i < $n; $i++) {
$temp = $arr[$i];
$j = $i;
while ($j >= $gap && $arr[$j - $gap] < $temp) {
$arr[$j] = $arr[$j - $gap];
$j -= $gap;
}
$arr[$j] = $temp;
}
$gap = floor($gap / 2);
}
return $arr;
}
$numbers = [12, 34, 54, 2, 3];
$sortedDesc = shellSortDesc($numbers);
print_r($sortedDesc);
唯一的改变是将比较运算符从 > 更改为 <。 这使得算法按降序排序。
Shell 排序 vs 快速排序
让我们将 Shell 排序与快速排序进行比较，快速排序是最快的排序算法之一。 我们将使用一个大型数组来对两者进行基准测试。
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);
// Shell Sort benchmark
$start = microtime(true);
shellSort($largeArray);
$shellTime = microtime(true) - $start;
// Quick Sort benchmark
$start = microtime(true);
quickSort($largeArray);
$quickTime = microtime(true) - $start;
echo "Shell Sort time: " . number_format($shellTime, 6) . " seconds\n";
echo "Quick Sort time: " . number_format($quickTime, 6) . " seconds\n";
在典型运行中，对于大型数据集，快速排序将比 Shell 排序更快。 但是，Shell 排序在处理中等大小的数组或内存受限时具有优势，因为它是一种就地排序算法。
何时使用 Shell 排序
- 中等大小的数组： Shell 排序在对于简单排序来说太大但又不太大的数组上表现良好。
- 内存限制： 作为一个就地算法，它使用最少的额外内存。
- 部分排序的数据： 当数据已经部分有序时，它可以很有效。
来源
本教程介绍了 PHP 中的 Shell 排序算法，并提供了数字和文本数据的示例，包括与快速排序的性能比较。
作者
列出 所有 PHP 教程。