希尔排序是对插入排序的一种改进,也叫递减增量排序,算法过程中通过对增量值的递减调整,形成每一个增量值对应的一个或多个待排序分组,分别对分组执行插入排序,最后调整增量值为一,对最后的分组排序后即完成排序过程。
插入排序过程是从待排序集合中每次选择一个元素,通过不断比较和交换位置,移动到已排序集合的适当位置上。插入排序每次只排序一个元素,并且当前元素的排序完成后,对下一个元素的排序过程并无影响,而希尔排序完成某一个增量的排序后,对下一个增量的排序是有辅助作用的。
算法过程
希尔排序算法中有一个关键概念:增量(increment),或者称之为步长或间隔(gap)更容易理解,它的作用是将序列中间隔为增量值大小的元素,提出出来作为一个分组。例如间隔大小为 时,从第一个元素开始,以 为间隔取元素形成第一个分组,然后从第二个元素开始,以同样间隔取元素形成分组,直到形成 个分组,则原始序列的元素已全部分散在这 个分组里。
算法步骤:
- 根据增量 值大小,将序列拆分为 个分组
- 对每个分组执行插入排序算法,并对 值按指定规则调整大小
- 重复步骤 1, 2,直到 值为 0
示例
当初始序列为:[5, 3, 4, 0, 2, 1, 8, 6, 9, 7]
gap 值为 3 时
元素以 3 为间隔,拆分为 3 个分组,因为从第 4 个元素开始,后续所有元素都已经在三个分组里:
所以希尔排序就是将序列拆分为 个子序列,这里称之为分组,然后对每个分组执行插入排序。由此可知,希尔排序与插入排序的不同之处在于:希尔排序是不断的对分组进行排序,以此来完成最后的排序,而插入排序是直接对原始序列进行排序。并且希尔排序的最后一次排序一定是插入排序,因为最后一次排序的增量值为一。
希尔排序的复杂度影响因素就是增量值的调整规则。常见的增量值有 ,即对序列的长度不断折半作为增量大小。还有 ,在下面的示例中选择的就是这种方式。
step 1
序列为:[5, 3, 4, 0, 2, 1, 8, 6, 9, 7]
因为 为 10,,所以 初始值为 3,, 初始值为 7
因为 值为 7,所以序列被拆分为 7 个分组,分别为:
- [5, 6]
- [3, 9]
- [4, 7]
- [0]
- [2]
- [1]
- [8]
对每个分组执行插入排序,不过很明显可以发现一个情况,这 7 个分组都是有序状态的,所以序列状态不变。
step 2
序列为:[5, 3, 4, 0, 2, 1, 8, 6, 9, 7]
,,,
因为 值为 3,所以序列被拆分为 3 个分组,分别为:
- [5, 0, 8, 7]
- [3, 2, 6]
- [4, 1, 9]
对每个分组执行插入排序后,3 个分组变为:
- [0, 5, 7, 8]
- [2, 3, 6]
- [1, 4, 9]
以第 3 个分组为例,由 [4, 1, 9] 变为 [1, 4, 9],可以发现一个很明显的事实,在这个分组里,4 和 1 位置相差一,即只需要比较和交换一次即可确定这个元素的,而且这个顺序很可能在后续的排序过程中不会变化,相对于直接对原始序列执行插入排序算法,两个元素位置相差 3 而言,大大降低了比较和交换的次数。
当然,在不同的增量值变化规则中,可能会存在上一轮调整过的元素次序,在下一轮排序被颠倒的情况,不过总体上序列中元素是朝向有序的方向变化的,并且随着增量值的递减,序列将会变得越发有序,也就是说每一轮的排序,对下一轮都是有辅助作用的。而且给增量值的变化设定一个较为科学的规则,能够极大降低希尔排序的时间复杂度。
step 3
序列为:[0, 2, 1, 5, 3, 4, 7, 6, 9, 8]
,,,
因为 值为 1,所以序列只有 1 个分组,该轮排序过程完全等同于插入排序。
代码示例
def shellSort(arr):
k = int(math.log2(len(arr) + 1)) # 2^k - 1 <= len(arr)
while k > 0:
gap = 2 ** k - 1 # 间隔大小
for index in range(0, gap): # 分组的个数
for i in range(gap + index, len(arr), gap): # 对分组执行插入排序
tmp = arr[i]
while i > index and tmp < arr[i - gap]:
arr[i] = arr[i - gap]
i = i - gap
arr[i] = tmp
k = k - 1
示例代码中存在四层循环,最外层循环用于对增量值进行递减,确保希尔排序的最后一轮排序间隔大小为一,以此来保证排序的正确性。第二层循环是增量值对应的分组个数,第三和第四层循环结构基本与插入排序完全相同,作用就是对每个分组执行插入排序操作。
算法分析
希尔排序是一种不稳定排序算法,排序过程中,存在两个元素跨多个位置的替换。对于 个元素的序列,由插入排序的结论可知,插入排序的最好情况为序列处于已排序状态,每个元素的插入排序过程只需要进行一次比较即可,即 个元素的序列,排序的比较复杂度为 ,交换复杂度为 ;最坏情况为序列处于逆序状态,比较和交换复杂度为 。对于希尔排序而言,若分组的个数为 ,则每个分组的元素个数近似为 。
-
最好情况下希尔排序的每个增量值对应的比较次数 近似为:
...
...
...
因为 ,所以对于希尔排序,最好情况下的比较复杂度为 ,交换复杂度为 。 -
对于插入排序而言,最坏情况即为序列为逆序的状态,不过对于希尔排序,逆序并不一定为最坏情况,因为增量值的变化规则是人为设定的,所以不确定是否针对增量值的变化规则而特意设定一组序列。此处不妨以逆序作为示例分析一下希尔排序的复杂度。忽略每一轮排序对下一轮排序的影响,则有:
...
...
...
总时间复杂度为:。但是观察示例过程中 step 1 和 step 3 的序列,经过两轮排序后,step 3 的序列已经较 step 1 显得更为有序,所以从大方向看,每一轮的排序对下一轮的排序是有序辅助效果的。即使给出的初始序列为逆序状态,当增量值减为一的时候,此时的序列一定相对于最初状态有序很多。当增量值变化规则为 时,比较和交换的时间复杂度最坏为 。
希尔排序属于原地排序算法,不需要申请额外的存储空间。它是在插入排序的基础上进行了改进,实际就是除了最后的插入排序外,对多个子分组也执行了排序。所以看到该算法的第一印象就是,它额外做了这么多工作,复杂度应该大于插入排序才对。所以导致希尔排序最坏复杂度低于插入排序的原因就是,通过合理的增量值设置,可以将本来需要多次比较和交换才能调整到正确位置的元素,只需要很少次的比较和交换就可完成。
引用
Shellsort & Algorithmic Comparisons
What is the benefit of Shell Sort versus Insertion/Bubble Sort?
网友评论