插入排序和希尔排序的对比

插入排序

插⼊排序（英语： Insertion Sort） 是⼀种简单直观的排序算法。 它的⼯作原理是通过构建有序序列， 对于未排序数据， 在已排序序列中从后向前扫描， 找到相应位置并插⼊。 插⼊排序在实现上， 在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位， 为最新元素提供插⼊空间。

def insert_sort(lst):
    n=len(lst)
    if n == 1:
    	return lst
    for i in range(1,n):
        for j in range(i, 0, -1):
            if lst[j] < lst[j-1]:
            	lst[j], lst[j-1] = lst[j-1], lst[j]
    return lst

最坏时间复杂度

O(n^{2})

最优时间复杂度

O(n)

平均时间复杂度

O(n^{2})

空间复杂度

总共 O(n) ，需要辅助空间 O(1)

希尔排序

希尔排序(Shell Sort)是插⼊排序的⼀种。 也称缩⼩增量排序， 是直接插⼊排序算法的⼀种更⾼效的改进版本。 希尔排序是⾮稳定排序算法。 该⽅法因DL． Shell于1959年提出⽽得名。 希尔排序是把记录按下标的⼀定增量分组， 对每组使⽤直接插⼊排序算法排序； 随着增量逐渐减少， 每组包含的关键词越来越多， 当增量减⾄1时， 整个⽂件恰被分成⼀组， 算法便终⽌。
希尔排序的基本思想是： 将数组列在⼀个表中并对列分别进⾏插⼊排序，重复这过程， 不过每次⽤更⻓的列（步⻓更⻓了， 列数更少了） 来进⾏。最后整个表就只有⼀列了。 将数组转换⾄表是为了更好地理解这算法， 算法本身还是使⽤数组进⾏排序。

def shell_sort(list):
	n = len(list)
    # 初始步长
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            # 每个步长进行插入排序
            for j in range(i, 0, -1):
            	if list[j] < list[j-gap]:
						list[j], list[j-gap] = list[j-gap], list[j]
        gap = gap // 2
    return list

最坏时间复杂度

根据步长序列的不同而不同。已知最好的：O(nlog^2 n)

最优时间复杂度

O(n)

平均时间复杂度

根据步长序列的不同而不同。

空间复杂度

O(n)