Python数据结构与算法47：排序与查找：谢尔排序

注：本文如涉及到代码，均经过Python 3.7实际运行检验，保证其严谨性。

本文阅读时间约为5分钟。

这一节介绍的是谢尔排序(Shell Sort)。

谢尔排序(Shell Sort)

我们注意到插入排序的比对次数，在最好的情况下是 $O(n)$ ，且这种情况建立在列表已经排好序的基础之上。

实际上，列表越接近有序，插入排序的比对次数就越少。

根据这一事实，谢尔排序以插入排序的算法思路为基础，对无序表进行“间隔”划分子列表，每个子列表都执行插入排序。

一个谢尔排序的实例

以下图Pic-506-1为例，要对整个列表做排序，以3为间隔，即每3个相邻元素为一个子列表，来分割整个列表。

每个子列表分别使用插入排序算法来完成排序。

随着子列表排序的完成，整个列表会越来越接近有序，从而减少整体排序的比对次数。

Pic-505-1 谢尔排序的一个实例之一

谢尔排序接下去要做的事是，让间隔越来越小，从3到2，最后到1。

最后一趟，即当间隔为1时，谢尔排序就成了标准的插入排序。此时，由于前面各个子列表排序完成后，整个列表变得相对有序许多，所以，这一步只需要很少的几次数据项移动即可完成整个列表的完全排序。

如下图Pic-506-2所示：

Pic-505-2 谢尔排序的一个实例之二

谢尔排序的思路及代码实现

通过上述谢尔排序的实例，我们可以理清谢尔排序的思路：

设列表的长度为n，那么一般最开始，令子列表的间隔为n/2，每趟使得子列表的间隔减半，即n/4，n/8，……，直到间隔为1为止。

其代码实现如下：

# 谢尔排序的算法。

def shellSort(alist):
    sublistcount =  len(alist) // 2  # 令初始间隔为n/2。
    while sublistcount > 0:
        for startposition in range(sublistcount):  # 被间隔的子列表排序。
            gapInsertionSort(alist, startposition, sublistcount)
        
        print(f"After increments of size {sublistcount}, The list is {alist}.")
        
        sublistcount =  sublistcount // 2  # 每次都让间隔减半。

def gapInsertionSort(alist, start, gap):  # 带间隔(gap)的插入排序算法。
    for i in range(start + gap, len(alist), gap):
        currentvalue = alist[i]
        position = i
        
        while position >= gap and alist[position - gap] > currentvalue:
            alist[position] = alist[position - gap]
            position = position - gap
        
        alist[position] = currentvalue
        
l = [3, 5, 9, 0, 1, 2, 99, 87, 34]

shellSort(l)

<<<
After increments of size 4, The list is [1, 2, 9, 0, 3, 5, 99, 87, 34].
After increments of size 2, The list is [1, 0, 3, 2, 9, 5, 34, 87, 99].
After increments of size 1, The list is [0, 1, 2, 3, 5, 9, 34, 87, 99].
<<<

谢尔排序的算法分析

表面上看，谢尔排序以插入排序为基础，算法复杂度可能不会强到哪里去。
但实际上，由于每趟的子列表排序都使得原列表整体上更接近有序，而这个过程会减少许多插入排序需要的“无效”比对。所以，谢尔排序的算法复杂度比插入排序的算法复杂度要强一些。

对谢尔排序的算法复杂度的详尽分析比较复杂，在此不做具体展开。大致说来，谢尔排序的算法复杂度介于 $O(n)$ 和 $O(n^2)$ 之间。

如果将间隔保持在 $2^{k}-1$ (如1、3、5、15、31等)，其中k为整数，那么谢尔排序的时间复杂度约为 $O(n^{\frac{3}{2}})$ 。

To be continued.

Python数据结构与算法47：排序与查找：谢尔排序