希尔排序
思想
希尔排序是插入排序的一种,也称之为缩小增量排序
。希尔排序算法是直接插入排序算法的一种改进,减少了其复制的次数,速度要快很多。希尔排序是非稳定排序算法,实现过程:
- 将记录按照下标的一定增量进行分组,
对每个组进行插入排序
- 增量逐渐减少:当减少至1时,算法终止
栗子
假设步长为step,对[1, 8, 2, 9, 3, 7, 4, 6, 5]进行排序,步长一般是按照折半
进行选取
- 步长取4:对[1, 3, 5],[8, 7],[2, 4],[9, 6]三个序列,分别进行插入排序
- 步长取2:对上述排序的序列,步长取一半,再按照类似的方法进行排序
- 步长取1:重复上述操作
时间复杂度
- 最优时间复杂度:根据步长序列的不同而不同
- 最坏时间复杂度:$O(n^2)$
- 稳定性:不稳定
Python实现
1 | def shell_sort(alist): |
Golang实现
1 | package main |