最近准备去找工作，时隔几年又要把在学校时代压床底的算法掏出来吹吹灰尘了，真有种朝花夕拾的感觉…哈哈哈哈
毕竟如果面试要是写不出来，那真是太尴尬了。
写那么一波插入排序找找感觉2333

运行环境 Runtime environment

1
2
3
操作系统： Windos10  
IDE: JetBrains Python 2018.2.4 x64  
语言: Python 3.66

背景

基础排序算法的一种咯，回忆一下也好。那要万一用上了呢？而且它是希尔排序的基础..当然希尔排序我也忘得差不多了。

插入排序

1
2
3
4
5
6
7
8
9
10
11
def insert_sort(nums):
    for i in range(1, len(nums)):   # 从第二个元素索引开始遍历
        temp = nums[i]  # 取出对应索引的元素
        last = 0
        for j in range(i-1, -1, -1):    # 倒着取值，与之前插过的元素逐一比对
            if nums[j] > temp:  # 若取出的元素前边的元素小，则对换位置
                nums[j + 1] = nums[j]
            else:
                last = j + 1
                break
        nums[last] = temp

总结

  1. 第一个数肯定是有序的，然后从第二个开始，从此往后遍历，把这个数插入到合适的位置，比第二个数大的一次往后面移动。
  2. 第二个数移动正确的位置之后，前两个数就是有序的，依次把后面的数按照刚才的方法插入到合适的位置，整个数组就变成有序的了。