插入排序与希尔排序

昵称11350173 2012-12-24

展开全文

首发传智播客IT论坛：http://bbs./thread-7315-1-1.html

先来插入排序：
假设我们需要排序的序列：

我们的排序思路是：
先，将序列分成两部分，一部分为排序好的序列，另一部分为未排序的序列，例如：

其中橙色的 4，6，7 是第一部分已经排序好的序列；黑色的3，9，5，8为第二部分，需要排序的部分。

其次，在第二部分为排序序列内取得一个元素，然后将其插入到这个已经排序好的序列内，例如：
将 3 插入到 4，6，7这个序列内，插入的结果为：

这样排序好的第一部分就变成了3，4，6，7；第二部分就变成了 9，5，8。

再次：这样以此类推，将所有未排序序列中的元素依次插入到这个排序好的序列内。当所有的未排序元素都插入成功后，我们的排序好的序列就是我们需要的排序结果。例如：
将9插入：

将5插入：

将8插入：

排序就成功了。
由于每次都是将一个元素插入到排序好的序列中，因此这个排序算法称之为 插入排序。

算法的思路就是这样了，可能大家会问：我们第一次是如何将一个序列拆分成两个部分的呢？也就是如何得到：

这个序列的呢？
其实很简单，我的说明是假设排序好的序列内已经存在了3个元素，大家可以试想，当我们第一次将序列分成两部分时，我们可以认为第一部分排序好的序列内只有一个元素，而其余的都在第二部未排序的序列内，就是：

大家可以看到当只有一个元素时，那么这个序列就是一个排序好的序列了吧。
因此我们需要做的第一件事情就是将 7 插入到4这个序列内，结果为：

下面的事情大家就应该清楚了吧，依次操作即可。

哦了，下面我们看看利用程序代码如何实现：
编程思路是这样的，使用双重循环完成，外层控制需要插入的元素，而内层控制每次插入时参与比较的元素。function insert_sort(&$arr) {
for($i=1, $len=count($arr); $i<$len; $i++) {
      $tmp = $arr[$i];
      for($j=$i-1; $j>=0 && $tmp < $arr[$j]; $j--) {
         $arr[$j+1] = $arr[$j];
      }
      $arr[$j+1] = $tmp;
}
}
上面的代码使用了引用传递。

经过上面的处理就完成了插入排序。

接下来，简单的分析一下这个算法。
在最好的情况下，也就是输入的序列本身也就是一个排序好的序列，那么这个算法的运行时间为O(N)，因为内层循环总是检测到break的情况。
但是如果输入的序列是一个逆序（就是从大到小的序列），那么执行的次数为1+2+。。+N，因此运行的时间为O(N^2)。
可以看出来，这个算法的执行时间的差别很大，执行时间取决于待排序序列中存在多少个逆序。

由此可知，当需要排序的序列是一个几乎被排序的序列（序列中的逆序较少）时，插入排序的效率还是相当可观的。

就说到这，引玉之砖，大家讨论。
还有一个希尔排序，也类似与插入排序，相当一个分组的插入排序，接下来会介绍。

希尔排序，这个名称源于希尔排序的发明者Donald Shell。

还是先说希尔排序的思路：
希尔排序的大体思路是：将一个未排序的序列分成多个组，然后在组内使用插入排序对组内序列排序。我们的分组方式是将每隔固定位置（增量）的元素分成一组。之后去调整这个间隔大小，重新分组，组内重新排序。直到分组的间隔为1，也就是所有的元素分成一组，再进行一次插入排序，这样就可以完成整个序列的排序过程。

下面描述以下这个过程：
假设我们需要排序的序列：

先将我们的序列分成几组，例如我们将每隔三个分成一组，那么分组的结果为：

然后我们在组内进行排序，排序的结果为：

从结果上看，我们可以发现每一组内的数据是按照顺序排序的，大家注意一个颜色的就是一个分组。

然后重新进行分组，例如分组的间隔改为了 2，那么分组的结果为：

在组内排序：结果为：

再次分组，标准为间隔为 1，那么分组结果为所有都是一组，然后在组内排序：
结果为：

这样经过这么几轮后，排序的效果就出来了。
注意，我们在组内进行排序时，是采用的插入排序算法（可以参考另一个贴子介绍插入排序）。

看到这可能会有些问题了，一个比较鲜明的就是：既然组内排序采用的是插入排序，而且我们最后也要将所有的元素分成一组，那不是相当于最后做了一次插入排序么，而且要比正规的插入排序，多出了好多轮其他分组情况的组内排序，为什么还有有真个排序方式呢？
大家还记不记得我们说插入排序后有一个小讨论了，具体可看插入排序介绍。我们讨论的结论是：插入排序的最好情况（没有逆序）时的复杂度为O(N)，而最坏情况（逆序为N*(n-1)/2）的复杂度为O(N^2)。基于这个结论，大家可以发现，我们在最后一次分成一组时，序列内的逆序（大数在小数前的两个数的组合，例如8,7)已经非常少，我么的例子中就一个，因此这个效率是很高的，要比直接进行插入排序的效率高呢。

大家还需要注意，注意以上的示例中，我使用的分组间隔为 3, 2, 1 。其实这个序列是任何最后一个元素为1的序列都可以。例如3，1 或者 4，2，1都可以。但是一定注意不同的序列产生的排序复杂度是不一样的，切记。
这个分组序列称之为希尔排序的增量序列，增量序列有一个非常流行的选择称之为希尔增量（希尔这个人建议的增量序列）：假设序列为ht...hk hk-1 .. h1 ，排序序列的长度为N，那么ht = N除以2的商，而hk-1 = hk 除以2的商，直到h1 = 1;
例如如果待排序数组的长度为 10，那么序列为 5, 2, 1;

下面我们就使用这个希尔增量来编写希尔排序的程序：
看代码，代码的实现步骤为：使用三层循环达到目的，最外层控制循环增量的值，里面两层使用插入排序的方法完成排序：

function shellSort(&$arr) {
$len = count($arr);
//确定增量序列
//php内没有整除采用floor向下去整
for($inc=floor($len/2); $inc>=1; $inc=floor($inc/2)) {
//内部实现与插入排序类似
//不过比较的元素取决于增量
for($i=$inc; $i<$len; ++$i) {
$tmp = $arr[$i];
for($j=$i-$inc; $j>=0 && $tmp<$arr[$j]; $j-=$inc) {
$arr[$j+$inc] = $arr[$j];
}
$arr[$j+$inc] = $tmp;
}
}
}

复制代码

上面的代码就实现了一个基于希尔增量的希尔排序。

还有需要大家注意，虽然在示例代码内，我们使用的是希尔增量（感觉好像最正宗），但是在实际的操作中，希尔增量并不是一个最好的增量序列，比较常用的其他序列有：
希尔增量（程序里使用的）：N/2 N/2/2 N/2/2 N/2/2../2 1 (/为整除的意思），这个增量的最坏情形是O(N^2);
Hibbard增量：2^k - 1 ，2^k-1 - 1, .... 2^2 - 1 , 2^1 -1；这个增量的最坏情形是O(N^3/2)
还有一个被认为是目前最好的增量序列：.... 109, 41, 19, 5, 1 其中每项是9*4^i - 9*2^i + 1与 4^i - 3*2^i + 1值内比较小的一个。
但是还有可能出现更好是序列，应该是数学问题了。
大家如果希望使用其他序列作为程序实现，大可以将这个序列放入一个数组内，然后将最外层循环改为遍历这个序列，然后达到目录：
例如：