插入排序

标签（空格分隔）： python-排序算法

一、直接插入排序

1、原理

再末排序序列中，构建一个子排序序列，知道全部数据排序完成；
再待排序的数，插入到已经排序的序列中合适的位置
增加一个哨兵，放入待比较值，让它和后面已经排好序的序列比较，找到合适的插入位置

2、排序思想

1、增加一个哨兵位，每轮比较将待比较数放入
2、哨兵一次和待比较数的前一个数据比较，大数靠右移动，找到哨兵中值的插入位置
3、每一轮结束后，得到一个从开始到带比较数位置的一个有序序列

3、代码实现

lst = [7, 9, 2, 5, 3, 1]

# 直接插入排序 - 升序排列

newlst = lst[:]         # 原样拷贝一份数据
newlst = [0] + newlst   # 增加一个哨兵位
length = len(newlst)

for i in range(2, length):
    newlst[0] = newlst[i]

    # 确定排序数据的有序区
    j = i-1

    if newlst[j] > newlst[0]: # 此处可以控制不会越界
        while newlst[j] > newlst[0]:
            newlst[j+1] = newlst[j]
            print("----", newlst)
            j -= 1
        newlst[j+1] = newlst[0]

    print("--", newlst)
print(newlst[1:])

4、总结

• 1、最好的情况: 正好是升序排列，则迭代并比较 n-1 次
• 2、最差的情况: 正好是降序排列，则迭代并比较n(n-1)/2 次
• 3、时间复杂度:
  • 使用两层嵌套循环，时间复杂度为： O(n**2)
• 4、稳定排序算法；
  • 稳定的意思是: [2, 1, 1, 3], 使用直接插入排序，第一个元素1，排序完，一定在第二个元素1的左边； 冒泡法和选择排序则不能保证
• 5、适用场景
  • 比较适合数据规模比较小的情况下；大数据规模下会发生大量的数据移动的操作，因此并不适合大规模的数据排序
• 6、优化点
  • 如果比较操作耗时大的话，可以采用二分法来提高效率。即二分查找插入排序。
  • 这里之所以能够引入二分，是因为插入排序会确定一个有序区，二分法的前提必须是数据有序

直接插入排序

原文：https://www.cnblogs.com/jingru-QAQ/p/11421337.html