python算法-插入排序

直接插入排序 Direct Insertion Sort

• 直接插入排序原理
  • 在未排序序列中，构建一个子排序序列，直至全部数据排序完成
  • 将待排序的数，插入到已经排序的序列中合适的位置
  • 增加一个哨兵，放入待比较值，让它和后面已经排好序的序列比较，找到合适的插入点

• 初始的0及下面开头的红色数字为哨兵，即待插入值

• 从第二个数字开始排序，即9

• 第一趟，哨兵是9，用1和哨兵比较，1小，哨兵插入，本轮比较结束

• 第二趟，哨兵是8，用9和哨兵比较大于哨兵，9向右移，1和哨兵比较，1小，哨兵插入本轮比较结束

• 以此类推，直至把最后一个数字放到哨兵并比较，插入完成

m_list = [[1,9,8,5,6,7,4,3,2],[1,2,3,4,5,6,7,8,9],[9,8,7,6,5,4,3,2,1],[1,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1,2]]
nums = [0] + m_list[0]    # nums为[0,1,9,8,5,6,7,4,3,2]
# print(nums)
sentinel,*origin = nums   # 哨兵位，待比较数字。sentinel为0，origin为[1,9,8,5,6,7,4,3,2]
# print(sentinel)
# print(origin)
count_swap = 0   # 计算每轮循环中，与哨兵位比较后要交换的次数
count_iter = 0   # 计算从第二个数字到最后一个数字，一共要循环的资源
length = len(nums)
for i in range(2,length):   # 从m_list[0]的第二个数字开始，第一个数字是待比较数字
    nums[0] = nums[i]    
# 放置哨兵，把比较的数字赋值给第一个数字，第一个数字就是哨兵位。如第一次就是把9放到哨兵位。这里的哨兵是在按列表中的数字不停顺序变化的，
# ，第一次是9，之后是8,5,6，一直到最后，如果要比较的数字比哨兵位的数字小，就不动，如果比哨兵位的数字大，就向右移
    j = i - 1    # 得出要比较数字的索引位置，下面就要用1和9比较
    count_iter += 1
    if nums[j] > nums[0]:    # 大数右移，找到插入位置。如果要比较的数字比哨兵位的数字大
        while nums[j] > nums[0]:
            nums[j+1] = nums[j]    # 依次右移
            j -= 1
# 如果索引j比哨兵位的数字大，就把索引j向后移一个位置，之后把索引j减1，再进行同样的比较。当8是哨兵位时，9与8比较，因为比8大，就会把9
# 的索引向后移动，之后再用1和哨兵位的8比较，1小于8,那么执行下面的哨兵插入，这时正好插入到了之前9的位置
            count_swap += 1
        nums[j+1] = nums[0]    # 将哨兵插入，注意插入在右侧要+1
print(nums, count_swap, count_iter)
输出：
[2, 1, 2, 3, 4, 5, 6, 7, 8, 9] 25 8
# 可以看到最后一个数字2在哨兵位上。

• 增加一个哨兵位，每轮比较将待比较数放入
• 哨兵依次和待比较数的前一个数据比较，大数向右移动，找到哨兵中值的插入位置
• 每一轮结束后，得到一个从开始到待比较数位置的一个有序序列，如上面第一次的有序序列是1,9，第二次是1,8,9
• 最好情况，正好是升序排列，比较迭代n-1次
• 最差情况，正好是降序排列，比较迭代1,2,…,n-1即n(n-1)/2
• 使用两层嵌套循环，时间复杂度O(n^2)
• 稳定排序算法
• 使用在小规模数据比较
• 优化
  • 如果比较操作耗时大的话，可以采用二分查找来提高效率，即二分查找插入排序

测试

=======================================================================================
代码编写过程：
1. 向列表元素中加入哨兵位的位置
2. 计算需要循环的次数
3. 开始循环，从原列表中第二个数字开始插入哨兵位
4. 设置待比较数字的索引值，将第二个数字放到哨兵位
5. 判断待比较数字是否大于哨兵位数字，如果不大于就结束本轮循环
6. 如果待比较数字是否大于哨兵位数字，就进入将循环，把待比较数字的索引加1或叫向后移
7. 将待比较数字的索引值减1，这是为了设置下一个待比较的数字，直到待比较数字不大于哨兵位数字
8. 将哨兵位数字插入到目前待比较数字的后面
9. 这个代码中，每次比较的都是用哨兵位上数字之前的数字和哨兵位上的数字相比
=======================================================================================
m_list = [[1,9,8,5,6,7,4,3,2],[1,2,3,4,5,6,7,8,9],[9,8,7,6,5,4,3,2,1],[1,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1,2]]
nums = [0] + m_list[0]   # 没有优化方法，无论如何都要跑完整个过程
sentinel,*origin = nums  # 这一句没有意义，但是可以看出解构的方法
count_swap = 0
count_iter = 0
length = len(nums)   # 这步是为了计算循环的次数
for i in range(2,length):   # 从实际的第二个数字开始
    nums[0] = nums[i]   # 把第二个数字开始插入哨兵位
    j = i - 1   # 设置待比较数字的索引
    count_iter += 1
    print("count_iter",nums)
    if nums[j] > nums[0]:   
# 如果待比较数字大于哨兵位数字，第一次这里的nums[j]是1，nums[0]是9，所以直接进入下一轮循环，第二次nums[j]是9，nums[0]是8。
        while nums[j] > nums[0]:   
        # 待比较数字大于哨兵位数字时，第二次nums[j]是9，nums[0]是8时进入
            nums[j+1] = nums[j]    
            # 把nums[j]是9赋值给nums[j+1]也就是把9后移一个位置，到8的位置
            j -= 1    
        # 索引减1，方便下次比较。下一次到while处，看nums[j]是否大于nums[0]，这时nums[j]是1，nums[0]是8，退出本轮循环
            print("count_swap",nums)
            count_swap += 1
        nums[j+1] = nums[0]  
# 这里一定是将哨兵位的数字插入到j+1索引上，一是j已经减1了，二是新的j+1的位置就是上一个j索引的位置，这时
# 的j+1和j+2索引位置是同一数字，所以插入到j+1的位置正合适。可以看一下下面输出的内容
print(nums,count_swap,count_iter)
输出：
count_iter [0, 1, 9, 8, 5, 6, 7, 4, 3, 2]
count_iter [9, 1, 9, 8, 5, 6, 7, 4, 3, 2]
count_swap [8, 1, 9, 9, 5, 6, 7, 4, 3, 2]   # 第一次进入循环比较，8在哨兵位，用9和8比较后移
count_iter [8, 1, 8, 9, 5, 6, 7, 4, 3, 2]
count_swap [5, 1, 8, 9, 9, 6, 7, 4, 3, 2]   
# 第二次进入循环后5在哨兵位，比较后9和8都后移，之后把5插入
count_swap [5, 1, 8, 8, 9, 6, 7, 4, 3, 2]
count_iter [5, 1, 5, 8, 9, 6, 7, 4, 3, 2]
count_swap [6, 1, 5, 8, 9, 9, 7, 4, 3, 2]
count_swap [6, 1, 5, 8, 8, 9, 7, 4, 3, 2]
count_iter [6, 1, 5, 6, 8, 9, 7, 4, 3, 2]
count_swap [7, 1, 5, 6, 8, 9, 9, 4, 3, 2]
count_swap [7, 1, 5, 6, 8, 8, 9, 4, 3, 2]
count_iter [7, 1, 5, 6, 7, 8, 9, 4, 3, 2]
count_swap [4, 1, 5, 6, 7, 8, 9, 9, 3, 2]
count_swap [4, 1, 5, 6, 7, 8, 8, 9, 3, 2]
count_swap [4, 1, 5, 6, 7, 7, 8, 9, 3, 2]
count_swap [4, 1, 5, 6, 6, 7, 8, 9, 3, 2]
count_swap [4, 1, 5, 5, 6, 7, 8, 9, 3, 2]
count_iter [4, 1, 4, 5, 6, 7, 8, 9, 3, 2]
count_swap [3, 1, 4, 5, 6, 7, 8, 9, 9, 2]
count_swap [3, 1, 4, 5, 6, 7, 8, 8, 9, 2]
count_swap [3, 1, 4, 5, 6, 7, 7, 8, 9, 2]
count_swap [3, 1, 4, 5, 6, 6, 7, 8, 9, 2]
count_swap [3, 1, 4, 5, 5, 6, 7, 8, 9, 2]
count_swap [3, 1, 4, 4, 5, 6, 7, 8, 9, 2]
count_iter [3, 1, 3, 4, 5, 6, 7, 8, 9, 2]
count_swap [2, 1, 3, 4, 5, 6, 7, 8, 9, 9]
count_swap [2, 1, 3, 4, 5, 6, 7, 8, 8, 9]
count_swap [2, 1, 3, 4, 5, 6, 7, 7, 8, 9]
count_swap [2, 1, 3, 4, 5, 6, 6, 7, 8, 9]
count_swap [2, 1, 3, 4, 5, 5, 6, 7, 8, 9]
count_swap [2, 1, 3, 4, 4, 5, 6, 7, 8, 9]
count_swap [2, 1, 3, 3, 4, 5, 6, 7, 8, 9]
[2, 1, 2, 3, 4, 5, 6, 7, 8, 9] 25 8