Swift算法-希尔排序Shell Sort

声明：算法和数据结构的文章均是作者从github上翻译过来，为方便大家阅读。如果英语阅读能力强的朋友，可以直接到swift算法俱乐部查看所有原文，以便快速学习。作者同时也在学习中，欢迎交流

希尔排序是基于插值排序的算法，通过将原始数据分为总数更小的几个小数组，并在这些小数组中整理排序的方式来提升插值排序的性能。

这里有一个模仿希尔算法执行过程的表演-匈牙利某大学传统舞蹈小视屏

执行原理

与插值排序通过对比相邻的两个元素的大小并在必要时候交换位置，希尔排序是通过比较相隔很远的两个元素。

两个元素之间的距离称为间隔。如果两个元素在比较之后需要交换位置，则直接更换彼此的位置。这个过程减少了插值排序中很多不必要的中间复制过程，即从两个元素更换位置前需要不断交换相邻元素的位置直到目的位置。
这里的最主要的思想就是，元素通过每次移动较大间隔，整个数组可以快速形成局部排序好的情况。这个会让接下来的交换变得更加快速。因为元素之间不需要进行过多次的位置交换。

一旦某一距离长度的间隔比值交换完成，间隔会变得越来越小，然后进行相应间隔的比值交换，这样的过程不断重复，直到间隔为1，也就是与插值排序同样过程的情况。然而，在希尔排序中，由于大部分数据在此时已经整理完毕，所以最后间隔为1的比值交换速度非常快。

例子

假设我们要用希尔排序对数组[64, 20, 50, 33, 72, 10, 23, -1, 4]进行整理。
我们从间隔为数组长度二分一开始：

n = floor(9/2) = 4

我们创建n个子数组。在每一个数组中，不同元素之间的间隔距离为n。在我们的例子中中，我们需要创建4个这样的数组。这些数据会通过insertionSort()函数进行整理排序。我们可以通过图表进行深入了解：

sublist 0:  [ 64, xx, xx, xx, 72, xx, xx, xx, 4  ]
sublist 1:  [ xx, 20, xx, xx, xx, 10, xx, xx, xx ]
sublist 2:  [ xx, xx, 50, xx, xx, xx, 23, xx, xx ]
sublist 3:  [ xx, xx, xx, 33, xx, xx, xx, -1, xx ]

如图所示，每一个子数组里面只包含原数组中每一个第4个元素。其他非第4元素的用xx表示。所以第一个子数组为[64,72,4]，第二个为[20,10],以此类推。这里我们使用间隔的原因是我们不需要直接创建新的数组，所有的交换过程都在原始数组中完成。

现在我们开始使用insertionSort()函数进行每个子数组的整理排序。比如第一个子数组中，我们需要先将4和72交换位置，然后是4和64，然后72大于64不需要交换。整理后的第一个子数组为：
sublist 0: [ 4, xx, xx, xx, 64, xx, xx, xx, 72 ]
其他子数组也完成同样过程，得到结果如下：

sublist 1:  [ xx, 10, xx, xx, xx, 20, xx, xx, xx ]
sublist 2:  [ xx, xx, 23, xx, xx, xx, 50, xx, xx ]
sublist 3:  [ xx, xx, xx, -1, xx, xx, xx, 33, xx ]

此时，从原数组中看，结果是这样的：
[ 4, 10, 23, -1, 64, 20, 50, 33, 72 ]
现阶段并不是完全整理好的，但是对比最早时候的数据，已经相对有序的多。现在第一次比值交换结束，我们开始进行第二次交换。将第一次的交换间隔除以2，得到第二次间隔2.
n = floor(4/2) = 2
这也意味着我们这次只需要创建两个子数组。

sublist 0:  [  4, xx, 23, xx, 64, xx, 50, xx, 72 ]
sublist 1:  [ xx, 10, xx, -1, xx, 20, xx, 33, xx ]

每个子数组包含间隔2的元素。重复之前的步骤，我们继续使用insertionSort()函数进行每个子数组的整理排序。结果如下：

sublist 0:  [  4, xx, 23, xx, 50, xx, 64, xx, 72 ]
sublist 1:  [ xx, -1, xx, 10, xx, 20, xx, 33, xx ]

通过观察我们可以发现，每一个子数组中均只有2个元素不在正确的位置上，所以在这一次的插值排序速度很快。

此时的原始数组为：
[ 4, -1, 23, 10, 50, 20, 64, 33, 72 ]
到这里第二次比值交换也结束，我们只需要进行最后一次比值交换，间隔为1：
n = floor(2/2) = 1
这也意味着这次的子数组个数为1，可以直接对当前的数组进行整理，继续使用insertionSort()函数。结果如下：
[ -1, 4, 10, 20, 23, 33, 50, 64, 72 ]
对希尔排序算法来说，大部分情况下它的性能是O(n^2)，当然运气好的时候是 O(n log n)。需要注意的是，希尔排序算法得到的是不稳定序列，它可能会对数值相同的两个元素进行位置交换。

间隔序列

间隔序列决定了间隔的初始值以及每次迭代过程中新的间隔值。对于希尔排序算法来说，一个好的间隔序列可以让整个算法表现的更好。

间隔序列的取值方法不是唯一的，在我们文中，我们采用的是整理数组个数的二分一，然后每次迭代继续除以二分一的策略。

代码

var arr = [64, 20, 50, 33, 72, 10, 23, -1, 4, 5]

public func shellSort(_ list: inout [Int]) {
    
    var sublistCount = list.count / 2
   
    while sublistCount > 0 {
        
        for index in 0..<list.count {
           
            guard index + sublistCount < list.count else { break }
            
            if list[index] > list[index + sublistCount] {
                swap(&list[index], &list[index + sublistCount])
            }
            
            guard sublistCount == 1 && index > 0 else { continue }
            
            if list[index - 1] > list[index] {
                swap(&list[index - 1], &list[index])
            }
        }
        sublistCount = sublistCount / 2
    }
}

shellSort(&arr)