Yangsanity's Blog

Life was like a box of chocolates

0%

希尔排序

发表于 分类于 阅读次数： Disqus：

在上一篇介绍插入排序的文章末尾，我们说通过插入排序算法可以引申出另一个重要的排序算法-希尔排序（shell sort），这篇文章我们就来说说希尔排序。

希尔排序也称为递减增量排序算法。希尔排序的名称是以美国计算机科学家 Donald Lewis Shell 的名字来命名，本文就选了他本人作为封面，1959年7月他在ACM通讯（Communications of the ACM，CACM）上发表了希尔排序算法。

希尔排序思想

在上一篇插入排序的文章中提到两点：

  1. 在数组近乎有序的情况下，插入排序的性能非常高，甚至可以达到线性的排序效率；

  2. 在插入排序中，每次都和之前的一个元素进行比较。

希尔排序就是基于这两点提出了改进方法。首先明确，希尔排序有个“步长”的概念，我们记为 step。接下来看看希尔排序是怎么改进的：

  1. 通过 step 将数组中的数据分组，同组之间的数据进行独立排序（这里排序的方法用的其实就是插入排序），这样可以让一个元素一次性地移动 step 个位置，朝它的最终位置前进一大步；

  2. 将 step 逐渐缩小并进行排序，这样一步一步的将一个完全无序的数组变成一个近乎有序的数组；

  3. 最后当 step = 1 时，这时算法其实就变成了普通的插入排序，而数组此时也变成了近乎有序的数组，我们知道这种情况用插入排序会非常快。

可以发现，希尔排序的整体思路其实就是插入排序的延伸，而插入排序其实就是 step = 1 的希尔排序。

以23,10,4,1的步长序列进行希尔排序的过程（picture from Wikipedia）

接下来就用个简单的demo来演示一下整个过程吧。假设初始“步长”为数组长度，“步长”的计算方式为：step = 前一次step / 2，待排序数组如下：

2 5 4 8 7 9 1 6 3

第一轮比较和交换的详细过程为：
step = 4，数据分组情况如下（相同颜色为一组）：[2, 7, 3]，[5, 9]，[4, 1]，[8, 6]

2 5 4 8 7 9 1 6 3
（1）2 < 7，保持不变；5 < 9，保持不变；4 > 1，交换位置
2 5 1 8 7 9 4 6 3
（2）8 > 6，交换位置
2 5 1 6 7 9 4 8 3
（3）7 > 3，交换位置
2 5 1 6 3 9 4 8 7
至此，第一轮比较结束，可以发现分组后每个独立分组之间的元素都是有序的。

接下来每次新的一轮都要先更新 step = 前一次step / 2，具体的比较和交换过程和上面类似，就不赘述了。这里直接给出所有轮次的 step 和初始分组情况以及结果如下：
step = 4；[2, 7, 3]，[5, 9]，[4, 1]，[8, 6]

2 5 1 6 3 9 4 8 7
step = 2；[2, 1, 3, 4, 7]，[5, 6, 9, 8]
1 5 2 6 3 8 4 9 7
step = 1；[1, 5, 2, 6, 3, 8, 4, 9, 7]
1 2 3 4 5 6 7 8 9

希尔排序代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * shellSort
 * @param data 待排序数组
 * @return 排序后的数组
 */
private int[] shellSort(int[] data) {
  int len = data.length, e, j, before;
  // 第一层循环控制每轮的步长
  for (int step = len / 2; step >= 1; step /= 2) {
    // 细心的同学肯定会发现：下面两层 for 循环的代码，当 step = 1 时，其实就是插入排序的代码
    // 这里直接用插入排序的优化版来写。当然也可以继续改写成用二分查找优化的版本（插入排序文章中已经介绍，有兴趣的同学可以自己改写）
    for (int i = step; i < len; i++) {
      e = data[i];
      for(j = i; (before = j - step) >= 0 && data[before] > e; j = before) {
        data[j] = data[before];
      }
      data[j] = e;
    }
  }
  return data;
}

希尔排序优化

在某些极端情况下，希尔排序是比插入排序还要慢的。比如下面这种情况，仍然假设初始“步长”为数组长度，“步长”的计算方式为：step = 前一次step / 2，待排序数组如下：

2 1 4 3 6 5 8 7

按照之前的思路来分析，会发现，第一轮 step = 4 和第二轮 step = 2 时，每个单独的分组内部的元素都没有进行任何交换，一直到 step = 1 时，数组才按照插入排序的方式进行排序。对于这样的数组，希尔排序反而白白增加了分组的成本。

造成这种情况的主要原因是：step 选择的不合适，因为我们使用的计算 step 的算法得到的“步长”是个等比序列，会出现了增量的盲区。所以，为希尔排序选择更有效的“步长”成为了优化的关键。

其实只要最终的步长为 1，那么任何步长序列都可以工作，因为当步长为 1 时，算法会变为普通插入排序，这就保证了数据一定会被排序。那如何选择更有效的“步长”呢？

其实这个问题我们不用太纠结，因为许多计算机科学家们提出了很多步长序列，其背后都有着复杂的推导过程。

这里介绍其中两种：

  1. 目前已知的最好步长序列。由Sedgewick提出的(1, 5, 19, 41, 109, …)，该序列的项来自 9 * 4 ^ i - 9 * 2 ^ i + 1 和 2 ^ (i + 2) * (2 ^ (i + 2) - 3) + 1 这两个算式。用这样步长序列的希尔排序比插入排序要快，甚至在小数组中比快速排序和堆排序还快；

  2. 在大数组中表现优异的步长序列。由斐波那契数列除去0和1将剩余的数以黄金分割比的两倍的幂进行运算得到的数列(1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713,…)

当然大家只需要了解即可，有兴趣的同学可以深究一下。

复杂度和稳定性分析

  1. 时间复杂度

  • 最优时间复杂度：O(n)

    • 类似于插入排序的最优时间复杂度分析。

  • 最坏时间复杂度：O(n^2)

  • 平均时间复杂度：根据步长序列的不同而不同。O(n * (logn)^2)

  1. 空间复杂度：O(1)
  • 整个过程都是原地排序，并没有用到其它辅助的空间。
  1. 希尔排序是一种不稳定排序。
  • 假如待排序数组为 [4, 4, 3, 5, 2]。其实也很好理解，虽然一次插入排序是稳定的，但在不同步长的插入排序过程中，相同的元素可能在各自的插入排序中被移动，就可能导致其稳定性被打乱。

欢迎关注我的其它发布渠道