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

环境

Python 3.5.2

原理

  • 为插入排序的优化
  • 对要排序的列表根据一定间隔(初始间隔一般设为列表长度的一半)进行分组
  • 对各列表之间相同位置(下标)的元素进行插入排序
  • 间隔减半,再次分组并对各列表之间相同位置(下标)的元素进行插入排序
  • 如此循环,最终间隔为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(n2)
  • 稳定性(多个元素等值的情况下是否会破坏原有顺序):不稳定

说点什么

  Subscribe  
提醒