php实现希尔排序

PHP实现希尔排序

希尔排序（Shell Sort）是插入排序的一种高效改进版本，通过将原始数组分割成多个子序列进行插入排序，逐步缩小子序列的间隔，最终完成排序。

希尔排序的基本思想

希尔排序通过引入“间隔”（gap）的概念，将数组分成若干子序列，对每个子序列进行插入排序。随着排序的进行，间隔逐渐减小，直到间隔为1时完成最后一次插入排序。

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;
}

// 示例用法
$array = [34, 2, 10, -9, 5, 7, 1, 0];
$sortedArray = shellSort($array);
print_r($sortedArray);

代码说明

• 初始间隔：通常选择数组长度的一半作为初始间隔（$gap），之后每次循环将间隔减半。
• 子序列排序：对于每个间隔，从$gap位置开始遍历数组，将当前元素与间隔前的元素比较，进行插入排序。
• 缩小间隔：每次外层循环后，间隔减半，直到间隔为1时完成最后一次插入排序。

时间复杂度分析

• 最好情况：当数组已经有序时，时间复杂度为 $O(n \log n)$。
• 最坏情况：当数组逆序时，时间复杂度为 $O(n^2)$。
• 平均情况：时间复杂度约为 $O(n^{1.3})$，具体取决于间隔序列的选择。

优化方向

• 间隔序列选择：使用更高效的间隔序列（如Hibbard序列、Sedgewick序列）可以进一步提升性能。
• 提前终止：在内层插入排序中，如果发现子序列已有序，可以提前终止以减少不必要的比较。

示例输出

对于输入数组 [34, 2, 10, -9, 5, 7, 1, 0]，输出结果为：

Array
(
    [0] => -9
    [1] => 0
    [2] => 1
    [3] => 2
    [4] => 5
    [5] => 7
    [6] => 10
    [7] => 34
)