直接插入排序

插入排序

标签（空格分隔）： 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、优化点
- 如果比较操作耗时大的话，可以采用二分法来提高效率。即二分查找插入排序。
- 这里之所以能够引入二分，是因为插入排序会确定一个有序区，二分法的前提必须是数据有序