谈谈插入排序(Insertion Sort)

在开始今天之前，先来看看影片（约2分钟）吧！

https://www.youtube.com/watch?v=OGzPmgsI-pQ

插入排序是从数列的左边开始，往右往右依次排序下去。过程中，左边的数一一完成排序，右边剩下尚未确认的数。在右边尚未搜寻的领域中取出一个数，插入已排序完成的领域中的适当位置。

若取出的数比排序完成领域中的所有的数都小，这个数移动到最左边之前，要进行比较和对调，第k回合必须进行k-1次的比较和对调的操作，因此最糟情况是第n回合发生n-1次的比较和对调，所以执行时间和气泡排序及选择排序一样是O(n^2)

import random

#从1-100中随机读取9个数字
nums = random.sample(range(1,100), 9)
print(nums)

# i控制j的上限值
for i in range(1, 9):
    #初始化变数nums[i]
    insert = nums[i]
    j = i-1
    #内层回圈从i-1到0，每次递减1
    while j>=0:
        if insert < nums[j]:
            nums[j+1]=nums[j]
        else:
            break 
        j = j-1
    #将变数insert储存到nums[j+1]
    nums[j+1]=insert
    print("插入排序执行次数为：", i ,"次")
    for item in nums:
        print(item,' ',end="")

插入排序法的最佳情况与最差情况：

1. 最佳情况：

   • 比较次数：O(n)
   • 设定次数：O(n)
   • 说明：假设资料要以由小到大排序，输入资料也是以小到大，则为最佳情况。

2. 最差情况：

   • 比较次数：O(n^2)
   • 设定次数：O(n^2)
   • 说明：假设资料要以由小到大排序，输入资料是以大到小，则为最差情况。