八大排序算法的Python实现__5__希尔排序

个人技术博客地址：http://songmingyao.com/

原理

• 为插入排序的优化
• 对要排序的列表根据一定间隔（初始间隔一般设为列表长度的一半）进行分组
• 对各列表之间相同位置（下标）的元素进行插入排序
• 间隔减半，再次分组并对各列表之间相同位置（下标）的元素进行插入排序
• 如此循环，最终间隔为1，即为正常的插入排序

源码

def shell_sort(l):
    n = len(l)
    # 初始间隔
    gap = n//2

    while gap > 0:
        for i in range(gap, n):
            for j in range(i, gap-1, -gap):
                if l[j] < l[j-gap]:
                    l[j], l[j-gap] = l[j-gap], l[j]
                else:
                    break
        gap //= 2


if __name__ == '__main__':
    l = [6, 5, 2, 8, 9, 4, 1, 0, 3, 7]
    print(l)
    shell_sort(l)
    print(l)

时间复杂度

• 最优时间复杂度（初始间隔为列表长度一半时）：O(nlogn)
• 最坏时间复杂度：O(n²)
• 稳定性（多个元素等值的情况下是否会破坏原有顺序）：不稳定