开源达人之PHP希尔排序DEMO

<?php

/**

 * 希尔排序演示

 * 使用Sedgewick增量序列实现希尔排序算法

 */

/**

 * 希尔排序函数

 *

 * 算法原理：

 * 1. 选择一个增量序列，本例使用Sedgewick序列 [5, 3, 1]

 * 2. 按照增量序列从大到小的顺序进行排序

 * 3. 每一轮排序时，将数组按照增量大小分组，对每组进行直接插入排序

 * 4. 当增量为1时，进行最后一次直接插入排序，完成整个排序过程

 *

 * @param array $arr 待排序的数组

 * @return array 排序后的数组

 */

function shellSort($arr)

{

    $n = count($arr);

    $sedgewick = [5, 3, 1]; // Sedgewick增量序列

    echo “原始数组: ” . implode(‘, ‘, $arr) . “\n”; //49, 38, 65, 97, 76, 13, 27, 49

    // 调整初始增量值，确保不超过数组长度

    $si = 0;

    while ($si < count($sedgewick) && $sedgewick[$si] >= $n) {

        $si++;

    }

// $numbers = [49, 38, 65, 97, 76, 13, 27, 49];

//             0   1   2   3   4   5   6   7

// 原始数组: 49, 38, 65, 97, 76, 13, 27, 49

// 增量: 13, 27, 49, 97, 76, 49, 38, 65

// 增量: 13, 27, 49, 38, 65, 49, 97, 76

// 增量: 13, 27, 38, 49, 49, 65, 76, 97

// 最终排序结果: 13, 27, 38, 49, 49, 65, 76, 97

    // 外层循环控制增量序列

    // $d=$sedgewick[0]/$d = 5;   条件5>0;  $d = $sedgewick[++0] = 1

    for ($d = $sedgewick[$si]; $d > 0; $d = $sedgewick[++$si]) {

        //echo $d.” +++++++++++++++++”; //  5/ 3/ 1

    //1-条件$d  $d = $sedgewick[$si]; $d > 0; $d = $sedgewick[++0] = 5;  / $d = $sedgewick[0]; $d=5>0;

    //2-条件$d  $d = $sedgewick[$si]; $d > 0; $d = $sedgewick[++0] = 3;  / $d = $sedgewick[1]; $d=3>0;

    //3-条件$d  $d = $sedgewick[$si]; $d > 0; $d = $sedgewick[++0] = 1;  / $d = $sedgewick[2]; $d=1>0;

        //1-$d=5

        //2-$d=3

        //3-$d=1

        // 中层循环从第d个元素开始，到数组末尾

        // 5/ 3/ 1/ < 8

        for ($p = $d; $p < $n; $p++) {

            $tmp = $arr[$p]; // 取出当前元素   V 13/ 97/ 38

            $i = $p; //   K 5/ 3/ 1

        //1-条件$p  $p = $d; $p < $n; $p++   /   $p = $d 5;  5 < 8;    $p++ 6++

        //2-条件$p  $p = $d; $p < $n; $p++   /   $p = $d 3;  3 < 8;    $p++ 7++

        //3-条件$p  $p = $d; $p < $n; $p++   /   $p = $d 1;  1 < 8;    $p++ 8++

            //1- $tmp = $arr[$p];   /    $tmp = $arr[5]=13;

            //   $i = $p;           /    $i = $p 5

            //2- $tmp = $arr[$p];   /    $tmp = $arr[6]=27;

            //   $i = $p;           /    $i = $p 6

            //3- $tmp = $arr[$p];   /    $tmp = $arr[7]=49;

            //   $i = $p;           /    $i = $p 7

            // 内层循环进行插入排序

            // 在当前分组中向前比较，如果前面的元素大于当前元素，则向前移动

            while ($i >= $d && $arr[$i – $d] > $tmp) {

                //echo $d.’****’;

                $arr[$i] = $arr[$i – $d]; // 元素向后移动

                $i -= $d; // 继续向前比较同一分组的元素

            //1-条件$i   $i >= $d && $arr[$i – $d] > $tmp     /     5 >= 5 && $arr[5-5] > 13    49 >13

            //2-条件$i   $i >= $d && $arr[$i – $d] > $tmp     /     6 >= 3 && $arr[6-3] > 27    97 >27

            //3-条件$i   $i >= $d && $arr[$i – $d] > $tmp     /     7 >= 1 && $arr[7-1] > 49    27 >49

                //1-$arr[$i] = $arr[$i – $d];       /     $arr[5] = $arr[5-5]   13 =49   交换

                //  $i -= $d;                       /     $i = 5 – 5 = 0;

                //2-$arr[$i] = $arr[$i – $d];       /     $arr[6] = $arr[6-3]   27 =97   交换

                //  $i -= $d;                       /     $i = 6 – 3 = 3;

                //3-$arr[$i] = $arr[$i – $d];       /     $arr[7] = $arr[7-1]   49 =27   交换

                //  $i -= $d;                       /     $i = 7 – 1 = 6;

            }

            //echo $i.’—————–‘;

            $arr[$i] = $tmp; // 将当前元素插入到正确位置

            //1-$arr[$i] = $tmp     /  $arr[5] = 13

            //1-$arr[$i] = $tmp     /  $arr[6] = 27

            //1-$arr[$i] = $tmp     /  $arr[7] = 49

        }

        echo “增量$d排序后: ” . implode(‘, ‘, $arr) . “\n”;

    }

    return $arr;

}

// 测试数据

$numbers = [49, 38, 65, 97, 76, 13, 27, 49];

//          0   1   2   3   4   5   6   7

echo “=================希尔排序演示=================\n”;

// 执行希尔排序

$sortedNumbers = shellSort($numbers);

echo “最终排序结果: ” . implode(‘, ‘, $sortedNumbers) . “\n”;

echo “=============================================\n”;

/**

 * 另一个更通用的希尔排序实现

 * 使用Knuth序列作为增量序列 (3^k – 1) / 2

 */

function shellSortKnuth($arr)

{

    $n = count($arr);

    // 计算Knuth序列的最大增量

    $gap = 1;

    while ($gap < $n / 3) {

        $gap = $gap * 3 + 1; // 1, 4, 13, 40, 121, …

    }

    echo “使用Knuth增量序列进行排序:\n”;

    echo “原始数组: ” . implode(‘, ‘, $arr) . “\n”;

    // 不断缩小增量，直到为1

    while ($gap >= 1) {

        echo “当前增量: $gap\n”;

        // 对每个分组执行插入排序

        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;

        }

        echo “增量$gap排序后: ” . implode(‘, ‘, $arr) . “\n”;

        $gap = (int)(($gap – 1) / 3); // 缩小增量

    }

    return $arr;

}

// 使用Knuth序列的希尔排序测试

echo “\n==============Knuth序列希尔排序==============\n”;

$numbers2 = [49, 38, 65, 97, 76, 13, 27, 49];

$sortedNumbers2 = shellSortKnuth($numbers2);

echo “最终排序结果: ” . implode(‘, ‘, $sortedNumbers2) . “\n”;

echo “=============================================\n”;

?>

这个希尔排序演示程序包含以下特点：

详细注释：每个关键步骤都有清晰的注释说明

过程可视化：在排序过程中输出每一步的结果，便于理解算法执行过程

两种实现：

第一种使用Sedgewick序列 [5, 3, 1]

第二种使用更通用的Knuth序列 (3^k – 1) / 2

清晰输出：显示原始数组、每轮增量排序后的结果和最终排序结果

当你运行这个程序时，会看到类似以下的输出：

=================希尔排序演示=================

原始数组: 49, 38, 65, 97, 76, 13, 27, 49

当前增量: 5

增量5排序后: 13, 38, 65, 97, 76, 49, 27, 49

当前增量: 3

增量3排序后: 13, 38, 27, 97, 76, 49, 65, 49

当前增量: 1

增量1排序后: 13, 27, 38, 49, 49, 65, 76, 97

最终排序结果: 13, 27, 38, 49, 49, 65, 76, 97

=============================================

这个演示可以帮助你更好地理解希尔排序的工作原理和执行过程。