[原创] Shell sort（希尔排序）笔记

『1』概述
希尔排序（Shell sort）是一种不常用的排序算法，因为它效率不算高，但是作为插入排序的改进算法之一，有必要了解一下。

• 时间复杂度：

最坏情况： $O\left( {{n^2}} \right)$
最好情况： $O\left( {n{{\log }^2}n} \right)$
平均情况： $O\left( {{n^{1.5}}} \right)$

• 是不是稳定排序算法：否
• 得名起源：1959年的时候Donald Shell发明的，所以叫Shell sort

『2』原理
首先，希尔排序是插入排序的改进版本。因此有必要回顾一下插入排序的做法：我们知道，插入排序总是把待排序的数组分割成两部分，其中第一部分有序，第二部分无序。有序部分一开始只包含数组中的第一个元素，然后取出无序部分的第一个元素，从有序部分的最后一个元素开始，与有序部分的元素相比，从而将其插入有序部分的正确位置。
这也就导致了，如果一个元素距离它的正确位置非常远（例如 9 5 6 7 2 4 3 8 1 这个数组，1这个数本应排在第一位，但是它在排序前是排在最后一位，因此它就离正确位置非常远了），那么我们就要做很多次大小比较，才能找出其正确位置，所以Donald Shell就想，能不能让这种距离正确位置很远的元素，一次就能跨越很大的距离，而不是要做那么多次比较才能找到正确位置呢？
可以的。试想一下，如果单独看数组中的9 2 1这几个元素，我们只需要花费很少的几次大小比较（因为只有3个元素），就可以用插入排序的方法，把1移动到正确的位置上。相对于整个待排序的数组来说（用插入排序把1移动到正确的位置需要很多次比较），这就相当于跨越了很大的距离。对于数组中所有的元素，我们都可以这样干，让它们都搭上“大跨步”的快车，这样就可以“迅速”地把很多元素放到了更接近正确位置的位置。
文章来源：http://www.codelast.com/
那有人会问了，在9 2 1这几个数中对1进行插入排序，确实很快，但是9 2 1这几个数是怎么挑选出来的呢？显然是按一定的规则从原数组中切分出来的。其实在这个例子中，就是把数组按间距4（或者称步长4）分成了几部分得到的：
9 5 6 7 2 4 3 8 1
9          2          1
   5          4
      6          3
         7          8
那么，分别对这4个子数组（9 2 1，5 4，6 3，7 8）进行插入排序，就可以高效地把一些元素（例如前面所说的 1）放到离正确位置很近的位置上（或者刚好就放到了正确的位置上）。
文章来源：http://www.codelast.com/
那又有人会说了，对 9 2 1 这个子数组排序后，得到了 1 2 9，1和9都恰巧处于排过序的原数组中的正确位置上了；但是2这个数就没有那么好运气了，假设数组记为a，则2应位于a[1]处，但是对 9 2 1 排序后，2实际上是位于a[4]处。对其他的子数组（5 4，6 3，7 8），也有同样的问题：我们分别把这些子数组排序后，再拼凑起来成为一个完整的数组（得到1 4 3 7 2 5 6 8 9）的话，并不能保证整个数组是有序的。
所以只进行一次切分原数组、并分别排序子数组，再合成一个大数组，并不能解决问题。所以，我们继续按更小的间距（或称为步长），把上面得到的、部分排序的子数组“合成”的大数组进行切分，这一次，我们把前一次的间距4除以2，也就是间距为2：
1 4 3 7 2 5 6 8 9
1    3    2    6    9
   4    7    5    8
这次再对 1 3 2 6 9，4 7 5 8 这两个子数组分别单独进行插入排序，得到 1 2 3 6 9 和 4 5 7 8，再合成为一个大数组：1 4 2 5 3 7 6 8 9。这个大数组仍然不是有序的。
文章来源：http://www.codelast.com/
于是我们最后一次，把间距（步长）再除以2，也就是间距为1，并对大数组进行切分：
1 4 2 5 3 7 6 8 9
1 4 2 5 3 7 6 8 9
由于间距已经缩到最小了，所以切分之后的子数组也就是切分之前的大数组，我们再对它进行插入排序，就一定可以得到完全有序的大数组了，至此，工作完成。
由于在前面的几步切分、排序的过程中，已经把一个可能原来“很无序”的数组，逐步地变成了一个“比较有序”的数组（虽然还不是完全有序的），并且我们知道，一个数组越有序，对其进行插入排序的效率就越高，因此，在前面的努力之下，我们通过最后一步切分、排序，就可以比较轻松地完成整个数组的排序了——正所谓“前人种树，后人乘凉”。
文章来源：http://www.codelast.com/
『3』时间复杂度
希尔排序的时间复杂度分析很复杂，如果你有兴趣，可以研读这篇文章。总之可以证明，其最坏情况下的时间复杂度是 $O\left( {{n^2}} \right)$ ，但是对希尔排序稍加一点改进，就可以使其时间复杂度提高到 $O\left( {{n^{1.5}}} \right)$ 。
怎么改进呢？参考前面的例子，我们会发现，在对数组进行第1次切分和第2次切分的过程中，我们分别得到了两个子数组 9 2 1 和 1 3 2 6 9，它们里面都含有 1 2 9 这三个元素。在第一次切分数组、排序之后，1 2 9 这三个元素已经是正确的顺序了，但是在第2次对数组进行切分、排序的时候，又对这三个元素进行了大小比较，这纯粹是浪费时间，因此，如果可以避免上一轮排序中子数组的所有元素进入下一轮排序中的子数组里，我们就可以避免做很多无用功。所以，只需要在间距（步长）为偶数值的时候，将其+1，就可以得到没有公因子的间距（步长）序列，避免了上面的不利情况。
文章来源：http://www.codelast.com/
正因为希尔排序的效率与间距（步长）有莫大的关系，因此，人们找到了各种高效的步长。如Wiki所说：

已知的最好步长串行是由Sedgewick提出的 (1, 5, 19, 41, 109,...)，该串行的项来自 $9 \times {4^i} - 9 \times {2^i} + 1$ 和 ${4^i} - 3 \times {2^i} + 1$  这两个算式。

其中， $i = 0,1,2, \cdots$ 时，第一个式子计算出的值分别为1，19，109，……； $i = 2,3, \cdots$ 时，第二个式子算出的值分别为5，41，……

文章来源：https://www.codelast.com/
➤➤ 版权声明 ➤➤ 
转载需注明出处：codelast.com 
感谢关注我的微信公众号（微信扫一扫）：