来源：swift-algorithm-club
希尔排序(Shell Sort)
希尔排序是插入排序的一种更高效的改进版本，方法是将原始列表分成较小的子列表，然后使用插入排序对其进行单独排序。
怎么运行的
插入排序是比较相连的元素，如果它们顺序不对就交换它们，而希尔排序算法会比较相距很远的元素。
元素之间的距离称为 gap。 如果被比较的元素的顺序错误，则它们会在 gap 中交换。 这消除了插入排序中常见的许多中间副本。
译注： gap已经被翻译成步长/增量/间距等，为了避免歧义，本文就不做翻译，直接写成gap
这个想法是，通过在大 gap 上移动元素，数组变得非常快速地部分排序。 这使得之后的排序过程更快，因为他们不再需要交换那么多项。
一轮完成后，gap变小，新一轮开始。 这将重复，直到 gap 大小为1，此时算法的功能就像插入排序一样。 但是由于数据已经很好地排序，所以最后一轮可以非常快。
例子
假设我们想使用希尔排序对数组 [64, 20, 50, 33, 72, 10, 23, -1, 4] 进行排序。
我们首先将数组的长度除以2：
n = floor(9/2) = 4
这是 gap 大小。
我们创建n子列表。 在每个子列表中，每一项的间隔是大小为n的gap 。 在我们的示例中，我们需要制作其中四个子列表。 子列表按insertionSort()函数排序。
这可能没有多大意义，所以让我们仔细看看会发生什么。
第一轮如下。 我们有n = 4，所以我们制作了四个子列表：
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的项。 不在子列表中的项用xx表示。 所以第一个子列表是[64,72,4]，第二个子列表是[20,10]，依此类推。 我们使用这个“gap”的原因是我们不必实际制作新的数组。 相反，我们将它们交织在原始数组中。
我们现在在每个子列表上调用一次insertionSort()。
插入排序的这个特定版本从后面到前面排序。子列表中的每个项目都与其他项目进行比较。如果它们的顺序错误，则交换值并一直向下移动，直到我们到达子列表的开头。
因此对于子列表0，我们将4与72交换，然后将4与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 ]
它还没有完全排序，但它比以前更加排序。 这完成了第一次轮操作。
在第二轮中，我们将 gap 大小除以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 ]
请注意，在每个列表中只有两个元素位置顺序不对（译注：sublist 0是64和50，sublist 1是10和-1）。 因此插入排序非常快。 那是因为我们已经在第一轮中对数组进行了一些排序。
总数组现在看起来像这样：
[ 4, -1, 23, 10, 50, 20, 64, 33, 72 ]
这样就完成了第二轮。 最后一轮的gap是：
n = floor(2/2) = 1
gap 大小为1表示我们只有一个子列表，即数组本身，我们再次调用insertionSort()对其进行排序。 最终排序的数组是：
[ -1, 4, 10, 20, 23, 33, 50, 64, 72 ]
在大多数情况下，希尔排序的性能为O(n^2)，如果幸运，则为 O(nlogn)。 该算法是不稳定的排序; 它可能会改变具有相等值的元素的相对顺序。
gap 序列
“ gap 序列”确定 gap 的初始大小以及每次迭代如何使 gap 变小。 良好的 gap 序列对于希尔排序表现良好非常重要。
上面实现例子中的 gap 序列是希尔原始版本中的 gap 序列：初始值是数组大小的一半，然后每次除以2。 还有其他方法可以计算 gap 序列
代码
希尔排序的Swift实现：
public func insertSort(_ list: inout[Int], start: Int, gap: Int) {
for i in stride(from: (start + gap), to: list.count, by: gap) {
let currentValue = list[I]
var pos = I
while pos >= gap && list[pos - gap] > currentValue {
list[pos] = list[pos - gap]
pos -= gap
}
list[pos] = currentValue
}
}
public func shellSort(_ list: inout [Int]) {
var sublistCount = list.count / 2
while sublistCount > 0 {
for pos in 0..<sublistCount {
insertionSort(&list, start: pos, gap: sublistCount)
}
sublistCount = sublistCount / 2
}
}
var arr = [64, 20, 50, 33, 72, 10, 23, -1, 4, 5]
shellSort(&arr)
网友评论