程序员须掌握的数据结构:希尔排序python代码实现

2018-10-3110:12:40数据结构与算法Comments1,927 views字数 823阅读模式

希尔排序,时间复杂度,介于O(n)~O(n^2),也可以认为是O(n^3/2),插入排序的改进,比较和移位较少,每次遍历都会生成一个"更有序"的子列表。12行,增量部分5行,插入部分7行。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7596.html

# 源码: https://github.com/SpikeKing/data_structure_with_python
def shell_sort(alist):
    """
    希尔排序
    1. 两部分,第1部分,计算增量gap和起始位置s_pos;
    2. 增量是累除2,s_pos是增量的遍历
    3. 增量插入排序,额外传入起始位置和增量;
    4. range的起始由起始位置+增量;
    5. 循环条件为大于等于增量,差值为增量
    6. 12行,增量部分5行,插入部分7行
    :param alist: 待排序alist
    :return: None
    """
    gap = len(alist) // 2
    while gap > 0:
        for s_pos in range(gap):
            insert_sort_gap(alist, s_pos, gap)
        gap = gap // 2


def insert_sort_gap(alist, s_pos, gap):
    """
    带增量的插入排序
    :param alist: 待排序alist
    :param s_pos: 起始位置
    :param gap: 增量
    :return: None
    """
    for i in range(s_pos + gap, len(alist), gap):
        cur_val = alist[i]
        pos = i
        while pos >= gap and alist[pos - gap] > cur_val:
            alist[pos] = alist[pos - gap]
            pos -= gap
        alist[pos] = cur_val


def test_of_shell_sort():
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    shell_sort(alist)
    print(alist)


if __name__ == '__main__':
    test_of_shell_sort()
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7596.html
  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/7596.html

Comment

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定