直接插入排序

发表于 | 分类于

直接插入排序原理：

  • 在未排序序列中，构建一个子排序序列，直至全部数据排序完成
  • 将待排序的数，插入到已经排序的序列中的合适的位置
  • 增加一个哨兵位，放入待排序比较值，让它和后面已经排好序的序列做比较，找到合适的插入点
    简单是说： 就是在无序区中构建一个空白有序区，然后一个一个将无序区的元素拿到有序区作比较，将这些比较的元素按照从小到大或者从大到小的循序插入到有序区中

实现代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
lst = [1,6,5,4,2,3,9,7,8]

lst = [0] + lst
length = len(lst)

for i in range(2,length):
    lst[0] = lst[i]
    j = i - 1
    if lst[j] > lst[0]:
        while lst[j] > lst[0]:
            lst[j + 1] = lst[j]
            lst[j] = lst[0]
            lst[j] = lst[0]
            j -= 1
        
lst[1:]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
  • 因为在列表头部添加了一个元素用于记录待交换元素，所以应该从索引为2的元素，开始，拿来和已经排序好的序列进行比较(认为6已经在排序空间了)
  • 由于无法判断已排序区到底排了几次，所以只能使用while循环，直到排序区的某个元素比待排序元素小时，表示在上一次插入过后，排序区已经排序完毕，这时就可以退出循环了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
lst = [1,6,5,4,2,3,9,7,8]
length = len(lst)
temp = 0

for i in range(1,length):
    temp = lst[i]
    j = i - 1
    if lst[j] > temp:
        while lst[j] > temp:
            lst[j+1],lst[j] = lst[j],temp
            j -= 1
            if j < 0:
                break
                
lst
[1, 2, 3, 4, 5, 6, 7, 8, 9]

总结

  • 最好情况，正好是升序排列，比较迭代次n-1次
  • 最差情况，正好是降序排列，比较迭代1，2，… n - 1 次即n(n-1)/2，数据移动会非常多
  • 使用两层嵌套循环，时间复杂度为O(n^2)
  • 属于稳定的排序算法
  • 使用在小规模数据比较时
  • 如果比较操作耗时大的话，可以采用二分查找来提高效率，即二分查找插入排序(由于每次比较还是要进行插入，所以优化效率不是那么高)
-------------本文结束感谢您的阅读-------------
0%