[Python知识库]python实现希尔排序(shell)

希尔排序

1. 算法思想:
   希尔排序(Shell Sort)是插入排序的一种.也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本.希尔排序是非稳定排序算法,希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止.
   希尔排序时间复杂度是 O(n^(1.3-2)),空间复杂度为常数阶 O(1).
   希尔排序没有时间复杂度为 O(n(logn)) 的快速排序算法快 ,因此对中等大小规模表现良好.
   但对规模非常大的数据排序不是最优选择,总之比一般 O(n^2 ) 复杂度的算法快得多.
2. 实现
   python版本 3.7.2

def shellSort(alist):
    sublistcount = len(alist) // 2
    while sublistcount > 0:
        for startposition in range(sublistcount):
            gapInsertionSort(alist, startposition, sublistcount)
        sublistcount = sublistcount // 2


def gapInsertionSort(alist, start, gap):
    for i in range(start + gap, len(alist), gap):
        currentvalue = alist[i]
        position = i
        while position >= gap and alist[position - gap] > currentvalue:
            alist[position] = alist[position - gap]
            position = position - gap
        alist[position] = currentvalue


list1 = [1, 22, 5, 4, 8, 9, 7, 5, 12, 1, 45, 6, 53, 4, 5, 46, 45]
shellSort(list1)

一个可以查看排序演示和较详细介绍的网站
点我查看排序的可视化演示

如有错误还望指出