希尔排序是一种基于插入排序的排序算法，通过先将数组分组，对每组进行局部排序，再逐渐减少组间隔，最终实现整体排序。它由 Donald Shell 在 1959 年提出，是插入排序的一种更高效的改进版本，特别适用于大规模数组排序。

目录

  1. 算法思路
  2. PHP 代码实现
  3. 时间复杂度分析
  4. 适用场景与优势
  5. 练习题
  6. 相关链接
  7. 参考资料

算法思路

希尔排序的核心在于使用间隔（gap）的概念，将待排序数组分割成若干个子数组，然后对各个子数组进行插入排序。随着算法的进行，逐步缩小间隔，直到间隔为 1，此时整个数组基本有序，最后一次插入排序即可完成全局排序。

  • 初始间隔：通常选用数组长度的一半作为初始间隔。
  • 分组排序：将数组按照当前间隔分成若干子数组，每个子数组进行独立的插入排序。
  • 逐步缩小间隔：更新间隔值，一般取 gap = gap/2，重复上述步骤。
  • 最终排序：当间隔减小到 1 时，整个数组已经近乎有序，此时进行一次标准插入排序即可完成排序。

PHP 代码实现

下面给出一个使用 PHP 实现希尔排序的示例代码：

<?php
function shellSort(array &$arr) {
    $n = count($arr);
    // 初始间隔设为数组长度的一半
    for ($gap = floor($n / 2); $gap > 0; $gap = floor($gap / 2)) {
        // 对每个分组执行插入排序
        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;
        }
    }
    return $arr;
}

// 测试
$data = [64, 34, 25, 12, 22, 11, 90];
echo "排序前: " . implode(", ", $data) . "\n";
shellSort($data);
echo "排序后: " . implode(", ", $data);
?>

输出：

排序前: 64, 34, 25, 12, 22, 11, 90
排序后: 11, 12, 22, 25, 34, 64, 90

时间复杂度分析

  • 最坏情况：O(n²)
    当数据排序极为不利时，希尔排序的比较和交换次数可能接近 O(n²)。
  • 平均情况：介于 O(n²) 与 O(n log n) 之间
    实际性能依赖于间隔序列的选择，不同的间隔序列会影响排序效率。
  • 最佳情况：O(n)
    如果数组已经接近有序，希尔排序可以非常快速完成排序。

空间复杂度：O(1)（原地排序，无需额外存储空间）

适用场景与优势

  • 数据量中等：对于中等规模的数据集，希尔排序常常比简单的插入排序和冒泡排序更高效。
  • 初步排序：在其他高效排序算法（如快速排序）之前进行预排序，能提升整体效率。
  • 内存有限：由于希尔排序是原地排序，所以在内存受限的情况下表现出色。
  • 可扩展性：不同的间隔序列选择可以根据实际情况进行优化，提升排序性能。

练习题

  1. 实现希尔排序的递归版本：尝试用递归思路重写希尔排序代码。
  2. 间隔序列优化：尝试使用 Knuth 序列（gap = gap * 3 + 1）或其他间隔序列改进希尔排序，并比较其与传统 gap/2 方式的性能。
  3. 排序稳定性分析：讨论希尔排序的稳定性问题，并通过代码验证不同输入数据下排序是否稳定。
  4. 多维数组排序：扩展希尔排序，使其能够对二维数组按指定列进行排序。

相关链接

🔗 GeeksforGeeks – Shell Sort
🔗 Algorithm Visualizer – Shell Sort
🔗 Wikipedia – Shell Sort

参考资料

  1. 《算法导论》—— Thomas H. Cormen 等
  2. 《数据结构与算法分析》—— Mark Allen Weiss
  3. GeeksforGeeks – Sorting Algorithms

希望这篇关于希尔排序的详细介绍和代码练习对你有所帮助！如果有其他算法需要讲解，欢迎继续提问。