动态可视化十大排序算法之插入排序
点击上方蓝字关注我们
插入排序
提到插入排序啊，其实我在很小的时候就学会了，而且一直在用，真不是我吹牛皮。我猜大部分读者肯定也是很小的时候就学会了。
但是呢，直到上了大学，学了数据结构与算法之后，才知道，哦，原来这叫插入排序啊。
有一种众里寻他千百度，蓦然回首，那人却在灯火阑珊处的感觉。不信的话你听我慢慢道来。
我想大部分人应该都打过扑克牌吧。小的时候我打牌技术那可谓是一流的,基本上没咋输过。无论是斗地主，还是打麻将。但是那时候呢？不像现在这样，可以在手机上玩。我们几个小伙伴坐在地上围成一个圈，打纸牌。
打扑克牌的时候需要先拿牌，而你每一步拿到的牌的大小又是随机的。但是我们在出牌的时候一般都会保持牌的有序性，这样显得比较直观明显，要不然地主出了牌，你光找自己有没有比他大的牌就要找很长时间，还有可能漏找，你可以想下自己是如何做的呢？是不是在拿牌的过程就直接把拿到的牌根据大小放到它应该放入的位置呢？这样牌拿完后，每个人手里的牌都是有序的，抓牌的过程就是插入排序。
看到这里，是不是觉得插入排序就很好理解了呢？而且你有没有觉得算法一直在我们生活中应用着，只不过很多时候我们没有察觉到而已。
老规矩，先简单介绍下插入排序的思想，然后看下插入排序算法执行的每一步。
思想
插入排序，顾名思义，关键的词就是插入，类比于选择排序，每次从待排序区间选择最小值和待排序区间的第一个元素进行交换；插入排序也是同样的套路，它同样把待排序元素分为已排序区间和待排序区间，每次从待排序区间选择第一个元素，插入到已排序区间的对应位置，可以脑补下自己抓牌的过程，这样，每次迭代下来，已排序区间的长度加
,未排序区间的长度减
,迭代
次，元素就会变得有序。
如果觉得不够直观的话，可以观看下面的视频。
代码实现
#!/usr/bin/python
# -*- coding: utf-8 -*-
from typing import List
import random
def insert_sort(array: List[int]) -> None:
if len(array) <= 1:
return
for i in range(1, len(array)):
temp = array[i]
index = i - 1
while index >= 0:
# 将待排序区间的第一个元素和已排序区间的元素进行从后往前比较（从前往后也可以）
if array[index] > temp:
# 如果小于当前元素，就进行移动
array[index + 1] = array[index]
index -= 1
else:
break
array[index+1] = temp
if __name__ == "__main__":
n = 15
min_number, max_number = 0, 100
array = [random.randint(min_number, max_number) for _ in range(n)]
print(array)
insert_sort(array)
print(array)
优化方法：二分查找插入排序
可以看到啊，插入排序的思想就是要在已排序区间中找到插入元素的位置，主要细节啊，在已排序区间查找第一个值大于给定值的元素位置，同理，在已排序区间查找最后一个值小于给定值的元素位置也可以。
这不就是我之前文章中提到的二分查找算法的变体问题吗？忘记的小伙伴可以查看下五千字长文带你学习 二分查找算法
既然已经找到了优化方法，那就看下如何实现吧！
#!/usr/bin/python
# -*- coding:utf-8 -*-
import random
from typing import List
# 二分查找插入排序算法
def insert_sort_optim(array: List[int]) -> None:
if len(array) < 1:
return
for i in range(1, len(array)):
# 进行二分查找，找到要插入的位置
index = binary_search(array, 0, i-1, array[i])
# print(array[i], index)
temp = array[i]
for j in range(i, index, -1):
array[j] = array[j - 1]
array[index] = temp
def binary_search(array, low, high, target):
while low <= high:
middle = low + ((high - low) >> 1)
if array[middle] > target:
if middle == 0 or array[middle - 1] < target:
return middle
else:
high = middle - 1
else:
low = middle + 1
# 和之前二分查找返回 -1 不同，如果查找不到，那就说明 target 是最大的，应该插入到最后
return high+1
if __name__ == "__main__":
n = 15
min_number, max_number = 0, 100
array = [random.randint(min_number, max_number) for _ in range(n)]
print(array)
insert_sort_optim(array)
print(array)
时间对比
接下来，我们对比下两种方法的运行时间。具体的代码我放在下面。
#!/usr/bin/python
# -*- coding: utf-8 -*-
from typing import List
import random
import time
def insert_sort(array: List[int]) -> None:
if len(array) <= 1:
return
for i in range(1, len(array)):
temp = array[i]
index = i - 1
while index >= 0:
# 将待排序区间的第一个元素和已排序区间的元素进行从后往前比较（从前往后也可以）
if array[index] > temp:
# 如果小于当前元素，就进行移动
array[index + 1] = array[index]
index -= 1
else:
break
array[index+1] = temp
def insert_sort_optim(array: List[int]) -> None:
if len(array) < 1:
return
for i in range(1, len(array)):
index = binary_search(array, 0, i-1, array[i])
# print(array[i], index)
temp = array[i]
for j in range(i, index, -1):
array[j] = array[j - 1]
array[index] = temp
def binary_search(array, low, high, target):
while low <= high:
middle = low + ((high - low) >> 1)
if array[middle] > target:
if middle == 0 or array[middle - 1] < target:
return middle
else:
high = middle - 1
else:
low = middle + 1
return high+1
if __name__ == "__main__":
n = 10000
min_number, max_number = 0, 10000
array = [random.randint(min_number, max_number) for _ in range(n)]
array1 = array[:]
start = time.perf_counter()
insert_sort(array)
end = time.perf_counter()
print("insert_sort costs {}s".format(end - start))
start = time.perf_counter()
insert_sort_optim(array1)
end = time.perf_counter()
print("insert_sort_optim costs {}s".format(end - start))
就是把上面两段代码进行了整理，放在了一个文件中。
对
个数据排序所需的时间
可以看到，使用二分查找进行优化后，程序的运行时间可以降低一半左右。虽然没有办法改变插入排序的时间复杂度，但已经将效率提升了一倍。
复杂度分析
无论是原始的插入排序，还是使用二分查找进行优化，时间复杂度都是：
，不知道有没有人会疑惑，那二分查找到底优化了哪里呢？因为找到插入位置后，搬移元素也需要
的时间复杂度。
确实是这样，不过呢，二分查找优化的地方就在于减少了元素的比较次数。你可以想想看，如果不进行二分查找的话，每次的比较操作次数就是
(当前外围循环数组的下标),但是进行二分查找后，每次的比较次数就变成了
,二分查找优化的地方就在于此。
空间复杂度的话，是
。
是稳定排序算法。
总结
好了，今天的插入排序就到这里了，插入排序在一些程序语言内置的排序函数中还有用到。比如说 Java 中的 sort 函数。
不要误会，不是说 sort 函数完全采用插入排序，而是当要排序数据在数据量非常小的情况下会使用。
虽然时间复杂度是
,但是并不代表运行时间一定比
的排序算法运行时间慢，因为时间复杂度代表的是一种趋势，忽略了系数，常量和低阶。
其实，对于插入排序的优化还有一种方法，叫做希尔排序。下篇文章我们一起来学习下。