Python数据结构与算法6——插入排序

插入算法

思想

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

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
  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