关于php:PHP数据结构插入类排序简单插入希尔排序

5次阅读

共计 2698 个字符，预计需要花费 7 分钟才能阅读完成。

总算进入咱们的排序相干算法的学习了。置信不论是零碎学习过的还是没有零碎学习过算法的敌人都会据说过许多十分闻名的排序算法，当然，咱们明天入门的内容并不是间接先从最常见的那个算法说起，而是依照肯定的规定一个一个的介绍。

首先，咱们要介绍的排序算法是插入类型的排序算法。顾名思义，插入排序就是将无序的一个或几个记录“插入”到有序的序列中，比拟典型的例子就是简略插入排序和希尔排序。

简略插入排序，也能够叫做间接插入排序。还是先看代码，再来进行下一步的解释。

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(n²)。同时，它是属于稳固的排序，什么叫稳固排序呢？仔细的同学应该发现了，在咱们的测试代码中，有两个雷同的数据，也就是 49。稳固的意思就是雷同的数据在排序前后的地位不会产生扭转，后面的 49 仍然是在前面的 49 后面。这就是排序的稳定性。

另外，简略插入排序比拟适宜初始记录根本有序的状况，当初始记录无序，n 较大时，这个算法的工夫复杂度会比拟高，不太适宜采纳。

简略插入排序很好了解吧，希尔排序又是什么鬼呢？别着急，从这个名字咱们是看不出什么端倪的，因为这个排序的名字是以它的发现者命名的。实际上，希尔排序还是一个插入排序的算法。

上文中说过，简略插入排序适宜根本有序的状况，而希尔排序就是为了晋升简略插入排序的效率而呈现的，它次要目标是缩小排序的 n 的大小以及通过几次排序就让数据造成根本有序的格局。

对于这个算法，咱们不能先上代码了，先来看图吧。

看明确了吗？咱们其实是将数据进行分组了，每次分组是以肯定的增量为根底的，比方咱们这个示意图中就是第一次以 5 为增量进行排序，第二次是以 3 为增量。这样第三次排序的时候，增量为 1，也就成为一个一般的简略插入排序了。一会咱们代码中就会体现进去。

还是按增量为迭代秩序进行这三趟排序的具体分析吧：

1）第一次迭代的时候，咱们将分组增量设置为 5，这时别离有三组数据，也就是 49 和 13，38 和 27，65 和 49，而后对这三组数据进行简略插入排序，之后的数组后果是 13、27、49、97、76、49、38、65。

2）第二次迭代，分组增量为 3，这时就分成了两组，每组三个数据，别离是 13、97、38 为一组，另一组是 27、76、65。对这两组数据进行简略插入排序之后更新数组后果为 13、27、49、38、65、49、97、76。

3）其实从两次分组排序之后就能够看出，这个数组曾经根本有序了。这时最初就是以分组增量 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 循环呀，它哪里晋升了效率了呢？其实希尔排序的效率晋升的确是无限的，它其实是通过前几次的分组让数据先根本有序。而在分组的状态中，数据比拟的数量并不会达到 n 的级别。当最初一次进行简略排序的时候，整个数据曾经是根本有序了，在这种状况下替换的次数显著也会缩小很多，所以它的工夫复杂度在现实状态下能够缩小到 O(log₂n)² 的程度。

排序的入门餐怎么样？咱们可不是间接就拿烂大巷的冒泡和快排上手的吧。不闻名不意味着不会用到，比方我面试的时候已经有个公司就是在面试题上写明了不能应用冒泡和快排。这时候，我置信简略插入排序直观好了解的个性肯定就能帮忙咱们度过这种面试难关了哦！

测试代码：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/7. 排序 /source/7.1 插入类排序：简略插入、希尔排序.php

参考文档：

本文示例选自《数据结构》第二版，严蔚敏

各自媒体平台均可搜寻【硬核项目经理】

正文完