PHP数据结构配置：简单输入，山排序

terry 2年前 (2023-09-27) 阅读数 71 #数据结构与算法

安装的排序算法是类型排序算法。顾名思义，排序涉及将一个或多个无序文件“放入”有序序列中。常见的例子有简单输入类型和希尔类型。

简单插入排序

简单插入排序也可以称为直接插入排序。我们先看一下代码，然后再解释下一步。

function InsertSort($arr)
{
    $n = count($arr);
    for ($i = 1; $i < $n; $i++) { // 开始循环，从第二个元素开始，下标为 1 的
        $tmp = $arr[$i]; // 取出未排序序列第一个元素
        for ($j = $i; $j > 0 && $arr[$j - 1] > $tmp; $j--) { // 判断从当前下标开始向前判断，如果前一个比当前元素大
            $arr[$j] = $arr[$j - 1]; // 依次移动元素
        }
        // 将元素放到合适的位置
        $arr[$j] = $tmp;
    }
    echo implode(', ', $arr), PHP_EOL;
}

InsertSort($numbers);

// 49, 38, 65, 97, 76, 13, 27, 49
// 13, 27, 38, 49, 49, 65, 76, 97

代码量不是很大，但是很容易理解。我们先用前两个测试数据来简单解释一下。

首先第一个循环是从1开始的，即取到的第一个无序元素是tmp = arr[1]，即现在tmp = 38。

然后循环开始。当前循环是判断当前j-1元素是否大于tmp元素。如果是，则进入循环体，arr[1] = arr[0]。到目前为止，arr[0] 和 arr[1] 都是 49。整个序列是49,49,65,...

最后让arr[0] = $tmp，等于38。（j--四舍五入时使用）。整个序列是38,49,65,...

通过下图，我们可以更清晰的看到整个序列的排序过程。

从上面的步骤可以看出，简单索引是一个从一侧开始，逐步对之前的数据进行排序的过程。从代码中可以看出，j在内循环中不断递减，并与之前排序好的数组进行比较。当它找到合适的位置时，会将数据放置在该位置。

从代码和分析来看，简单输入类型的时间复杂度为 O(n2) 。同时，它也是一个稳定的分类。什么是稳定排序？细心的同学应该看到，在我们的测试代码中有两个相同的数据集，即49。稳定是指同一组数据在排序前后位置不会发生变化，前面的49仍然在前面。 49在后面。这是稳定性的分类。

另外，一般组织第一条记录时，简单输入类型比较合适。当初始记录不稳定且n很大时，该算法的时间复杂度会很高，无法使用。

希尔排序

简单的输入排序很容易理解吧？什么是希尔排序？别担心，名字我们也不好说什么，因为这个分类是看到之后才命名的。事实上，山分类仍然是一种输入型算法。

如上所述，简单排序适用于基本组织的情况，而山排序似乎提高了简单排序的性能。其主要目的是通过多次排序和重分类来减小n的大小。让数据形成基本的结构化格式。

对于这个算法，我们不能先深入代码，我们先看图。

你明白吗？我们收集数据，每一组都基于一次促销。例如，在我们的图中，第一次以 5 为增量进行取，第二次以 3 为增量进行取。这样，当第三次取时，增量为 1 ，就变得相当简单了。输入类型。这很快就会反映在我们的代码中。

我们按照升序对这三个分类进行详细分析：

1）在第一轮中，我们将组增量设置为 5。 13、38 和 27、65 和 49，然后对这三个数据进行某种简单的整合。下一个数组的结果是 13, 27, 49, 97, 76, 49, 38, 65。

2) 在第二次迭代中，组增量为 3。现在，逐组除以 2 。有三个数据集，一组是13、97、38，另一组是27、76、65。这两个数据集简单分类后，更新为13、27、49、38、65 , 49, 97, 76 数组结果。但这个数组是一般顺序的。现在，最后一步就是随着组1的增加，再次进行简单排序。说白了，这最后一步就是一个简单的简单排序过程。

一步步解释之后就更清楚了。我再说一遍。希尔排序是一种按组进行的广泛输入类型，最后被简化为只有 1 增量的简单输入类型。我们再看一下代码：

function ShellSort($arr)
{
    $n = count($arr);
    $sedgewick = [5, 3, 1];

    // 初始的增量值不能超过待排序列的长度
    for ($si = 0; $sedgewick[$si] >= $n; $si++); 

    // 开始分组循环，依次按照 5 、3 、 1 进行分组
    for ($d = $sedgewick[$si]; $d > 0; $d = $sedgewick[++$si]) {
        // 获取当前的分组数量
        for ($p = $d; $p < $n; $p++) {
            $tmp = $arr[$p];
            // 插入排序开始，在当前组内
            for ($i = $p; $i >= $d && $arr[$i - $d] > $tmp; $i -= $d) {
                $arr[$i] = $arr[$i - $d];
            }
            $arr[$i] = $tmp;
        }
    }
    echo implode(', ', $arr), PHP_EOL;
}
ShellSort($numbers);

看代码，好像有三层for循环。如何提高绩效？事实上，Hill 分类的性能提升非常有限。它将数据组织成前几组。在聚类状态下，数据比较的次数没有达到n级。当简单的排序最终完成后，整个数据就大致组织好了。当然，在这种情况下，交易数量会大大减少，因此其时间复杂度可以降低到O(log，在最优水平n)2。