跟着动画学 Go 数据结构之希尔排序
希尔排序
在插入排序中,在待排序序列的记录个数比较少,而且基本有序,则排序的效率较高。
1959 年,Donald Shell 从“减少记录个数” 和 “基本有序” 两个方面对直接插入排序进行了改进,提出了希尔排序算法。
希尔排序又称为“缩小增量排序”。即将待排序记录按下标的一定增量分组(减少记录个数),对每组记录使用直接插入排序算法排序(达到基本有序);随着增量逐渐减少,每组包含的关键词越来越多,当增量减至 1,整个序列基本有序,再对全部记录进行一次直接插入排序。
算法思想
Shell 排序是一种高效的排序算法,基于插入排序算法。这种算法避免了插入排序中的大量移动,如果较小的值在最右边,就必须移到最左边。较小的值在最右边,必须移到最左边。
算法步骤:
设待排序的记录存储在数组
array[1...n]
中,增量序列为 {g1, g2, ..., gt}
, n>g1>g2>...>gt=1
。第一趟增量 g1, 所有间隔为 g1 的记录分在一组,对每组记录进行插入排序。
第二趟取增量 g2,所有间隔为 g2 的记录分在一组,对每组记录进行插入排序。
依次进行下去,直到所取增量 gt = 1,所有记录在一组中进行插入排序。
图解算法
假设我们有一个数组: [7, 4, 3, 5, 2, 1, 6]
:
第一次希尔排序间隔为 3 时:
第二次希尔排序间隔为 2 时:
第三次希尔排序间隔为 1 时:
Go 代码实现:
运行结果:
总结
时间复杂度:希尔排序的时间复杂度和增量序列有关,不同的增量序列其时间复杂度不同。当 n
处于某个特定的范围内,希尔排序的时间复杂度为 ,希尔排序复杂度的下界是 ,最坏情况下的时间复杂度为 ,但是,希尔排序还是没有快速排序快。
空间复杂度:希尔排序在分组进行插入排序时使用了一个辅助空间 j
,空间复杂度为
稳定性:希尔排序的分组导致不同组间的相同数字可能会调换位置,所以希尔排序是不稳定的排序算法。
版权声明: 本文为 InfoQ 作者【宇宙之一粟】的原创文章。
原文链接:【http://xie.infoq.cn/article/d59eeab0b6e5f907e055961eb】。
本文遵守【CC BY-NC】协议,转载请保留原文出处及本版权声明。
评论