Fork me on GitHub

【译】Swift算法俱乐部-希尔排序

本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Clubraywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目,目前在GitHub上有18000+⭐️,我初略统计了一下,大概有一百左右个的算法和数据结构,基本上常见的都包含了,是iOSer学习算法和数据结构不错的资源。
🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club,边学习边翻译的项目。由于能力有限,如发现错误或翻译不妥,请指正,欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️,🤩🤩🤩🤨🤪。
本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Shell Sort


希尔排序(Shell Sort)

希尔排序是插入排序的一种更高效的改进版本,方法是将原始列表分成较小的子列表,然后使用插入排序对其进行单独排序。

Sapientia大学创建了一个很好的视频,显示了匈牙利民间舞蹈的过程。(译注:类似希尔排序的过程,油管视频需要翻墙)

怎么运行的

插入排序是比较相连的元素,如果它们顺序不对就交换它们,而希尔排序算法会比较相距很远的元素。

元素之间的距离称为 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子列表。 在每个子列表中,每一项的间隔是大小为ngap 。 在我们的示例中,我们需要制作其中四个子列表。 子列表按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,我们将472交换,然后将464交换。 排序后,此子列表如下所示:

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 序列。

只是为了好玩…

这是 Matthijs 很久以前使用的一个旧的Commodore 64 BASIC版本的希尔排序,并且移植到他曾经使用的几乎所有编程语言中:

61200 REM S is the array to be sorted
61205 REM AS is the number of elements in S
61210 W1=AS
61220 IF W1<=0 THEN 61310
61230 W1=INT(W1/2): W2=AS-W1
61240 V=0
61250 FOR N1=0 TO W2-1
61260 W3=N1+W1
61270 IF S(N1)>S(W3) THEN SH=S(N1): S(N1)=S(W3): S(W3)=SH: V=1
61280 NEXT N1
61290 IF V>0 THEN 61240
61300 GOTO 61220
61310 RETURN

代码

希尔排序的Swift实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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)

扩展阅读

希尔排序的维基百科

Rosetta code的希尔排序(译注:大概70种不同语言实现希尔排序😅😓)

作者:Mike Taghavi,Matthijs Hollemans
翻译:Andy Ron
校对:Andy Ron


翻译后补充

希尔排序,也称递减增量排序算法,按其设计者希尔(Donald Shell)的名字命名,在1959年公布。

定义

希尔排序是将待排序的数组元素按下标的一定增量分组 ,分成多个子序列,然后对各个子序列进行直接插入排序算法排序;然后依次缩减增量再进行排序,直到增量为1时,进行最后一次直接插入排序,排序结束。

希尔排序的原理图

参考

图解排序算法(二)之希尔排序

排序:希尔排序(算法)

坚持原创技术分享,您的支持将鼓励我继续创作!