江苏龙网

  1. 主页 > 生活百科 > >

图解希尔排序，超详细非常好理解( 二 )

希尔排序


在实际的应用中，待排序的原序列可能有很多个元素，成千上万甚至上亿 。此时，为了充分利用希尔排序的效率，应该进行多趟排序，每一趟用不同的（严格说是递减的）增量对整个序列进行划分 。即首先用增量i1对原序列进行划分，并对每个子序列进行直接插入排序；然后对前一步得到的整个序列用一个新的且较小的增量i2（i2小于i1）进行划分，并对每个子序列进行直接插入排序；然后又对前一步得到的整个序列用一个更小的增量i3（i3小于i2）进行划分，并对每个子序列进行直接插入排序 。以此类推，直到最后增量为1，此时可以认为整个序列就是一个唯一的子序列，对它进行直接插入排序之后整个原始序列都是有序的了，希尔排序算法结束 。
根据这种增量划分子序列的方式，我们可知希尔排序是不稳定的排序算法 。假设原序列中有两个相同的元素，分别记为a和b，并且a在b的前面 。a和b很可能被划分到不同的子序列中，对子序列分别进行排序后，在整个序列中b可能移到了a的前面 。也就是说经过希尔排序后，原序列中原本相同的两个元素的相对位置在排序后发生了改变（原本是a在b之前，排序后是b在a之前），因此希尔排序是不稳定的排序算法 。
图3展示了一个完整的希尔排序算法过程，该示例中的希尔排序一共进行了3趟，每一趟的增量分别是3、2、1 。

图解希尔排序，超详细非常好理解

文章插图
图3 希尔排序完整过程
针对希尔排序，还有一个问题我们没有解决，那就是每一次希尔排序一共要进行多少趟，并且每一趟的增量是多少？每一趟的增量按照先后次序可以排成一个序列，称为增量序列 。增量序列不但决定了希尔排序的过程，并且也会影响希尔排序的性能 。
增量序列的最后一个元素必须是1，即希尔排序的最后一趟必须是在整个序列上进行直接插入排序，这样才能保证最终的序列是有序的 。最后一趟（即增量为1）开始时，整个序列都是大致有序的，因此这一趟只会进行少数元素的比较和移动 。
只要增量序列中的所有元素都从大到小排序，并且最后一个元素为1，那么该增量序列就可以用于希尔排序 。已经提出很多种增量序列，其中一种常用的增量序列可以根据公式2^(t - k + 1) - 1计算，参数t是一共要进行的趟数而k代表每一趟；1 ≤ k ≤ t，并且t ≤ ⌊log2(n+1)⌋，其中n是原序列的元素总数；该公式产生的增量序列为[... , 15, 7, 3, 1] 。
3. 对子序列排序进行并发执行在希尔排序的每一趟中，我们都需要对属于该趟的所有子序列进行排序，直到所有的子序列都是有序的 。按照我们上面的思路，我们是对所有子序列按串行的方式进行排序的，即先将第一个子序列排好序，然后将第二个子序列排好序，再将第三个子序列排好序 。以此类推，直到该趟中所有子序列都分别是有序的 。
这样在子序列之间按严格的先后顺序进行排序的方式是绝对正确的，也是十分直观的，它非常便于理解希尔排序的整体思想 。按照这样的方式也很容易用代码实现希尔排序，但在很多算法书中的实现代码却是按照并发的方式对子序列进行排序 。为了便于理解，我们假设进行希尔排序的计算机CPU是多核的并且它的核数多于子序列的数量，现在把每个子序列都分配给一个对应的核，并由该核对该子序列进行排序 。那么这些核可以同时运行以对所有子序列进行同时排序；这是可行的，因为每个子序列之间的元素都是独立而无重叠的，每个核之间的工作不会相互影响 。这种工作方式也叫做并行 。
再考虑单核CPU的情况，它依旧能够“同时”的执行多个任务，比如早期的分时操作系统就是运行在这样的环境下 。它先执行第一个任务的一部分，然后执行第二个任务的一部分，再执行第三个任务的一部分，等等 。某个时刻，它又会回来执行第一个任务的另一部分、然后又执行第二个任务的另一部分，等等 。这样CPU在多个任务之间快速切换，每个任务每次只占用很少的CPU时间；这样以我们人类的视角来看这些任务就好像是同时执行的，虽然实际上每个时刻只有一个任务在执行 。这种工作方式也叫做并发 。
只要将对每个子序列进行排序都视为一个单独的任务，那么很多希尔排序的实现方式都采用了这种并发的方式 。之所以这样做，可能是为了让实现代码更紧凑，或者利用按行顺序访问元素的方式减少高速缓存或内存页不命中的情况 。为了方便说明，这里我们假设原序列有n个元素，且某一趟的增量为i，并且n=i*m；那么该趟中整个序列将被划分为i个子序列且每个子序列有m个元素 。


推荐阅读


上一篇：TCP/IP 网络模型有几层？分别有什么用？

下一篇：python的面向对象编程