算法札记8——插入排序

插入算法

思想

  • 和选择排序类似的思想:将数据分成两个部分,排好序和待排序的部分。
  • 不同之处在于
    • 选择:从未排序的部分选择最小数据放到前面排好序的数据中
    • 插入:将未排序的部分第一个数据和前面的数据比较,插入相应的位置

https://www.cnblogs.com/onepixel/articles/7674659.html

栗子

将1看做是排好序的数据,后面是待排序的数据

[1,] [8, 9, 7, 3, 5, 2, 6, 4]

  • 第一步:待排序的数据第一个是8,比1大,放到1的后面
    [1, 8,] [9, 7, 3, 5, 2, 6, 4]
  • 第二步:待排序的第一个数据是9,比前面排好序的1和8都要大,所以排在8的后面
    [1, 8, 9,] [7, 3, 5, 2, 6, 4]
  • 第三步:待排序的第一个数据是7,放到1的后面
    [1, 7, 8, 9,] [3, 5, 2, 6, 4]
  • 以此类推......

    image.png
    image.png
    image.png
    image.png
    image.png
    image.png
    image.png

时间复杂度

  • 最优时间复杂度:
  • 最坏时间复杂度:
  • 稳定性:稳定

代码实现

def insert_sort(alist):

    # 插入排序

    n = len(alist)

    # 执行的总次数是从第二个元素到最后一个元素

    # 从右边的无序序列中取出多少个元素执行的过程

    for j in range(1, n):

        # i代表内层循环的起始值

        i = j

        # 从右边的无序序列中选出第一个元素,即下标为i的元素,插入前面的序列中

        # alist[i]和前面的每个元素进行比较,所以执行一次都要自减1

        

        # 只要i>0循环和比较要一直执行,直到等于0结束

        while i > 0:

            if alist[i] < alist[i-1]:

                alist[i], alist[i-1] = alist[i-1], alist[i]

                i -= 1

            # 结束比较,直接退出循环

            else:

                break

    return alist
# 方法二

def insert_sort1(alist):

    n = len(alist)

    for i in range(n):

        # 上面的方法中最开始i=j,执行自减操作,变成了:j-1, j-2,...,1

        # 内层写成for循环

        for j in range(i, 0, -1):

            if alist[j] < alist[j-1]:

                alist[j], alist[j-1] = alist[j-1], alist[j]

    return alist

本文由皮大大 创作,采用 知识共享署名-相同方式共享 3.0 中国大陆许可协议 进行许可。

转载、引用前需联系作者,并署名作者且注明文章出处。

本站文章版权归原作者及原出处所有 。内容为作者个人观点, 并不代表本站赞同其观点和对其真实性负责。本站是一个个人学习交流的平台,并不用于任何商业目的,如果有任何问题,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章