直接插入排序

直接插入排序是一种插入排序算法。

算法原理

它的原理是把n个待排序的元素看成一个有序表和一个无序表，开始的时候有序表中只含有一个元素，无序表中含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表中的元素进行比较，将它插入到有序表中适当的位置，使之成为新的有序表。

import random
import time
def insertion_sort(array):
    for i in range(1,len(array)):   #遍历无序表
        #设置终止条件
        while i>0:
            if array[i]>=array[i-1]:    #元素的值正确
                break
            else:
                array[i],array[i-1]=array[i-1],array[i]
                i-=1
    return array

#生成10000个值在0~10000的随机数
myList=[random.random()*10000 for i in range(10000)]
start_time=time.time()
print(insertion_sort(myList))
#统计使用时间
print(f"--- {time.time() - start_time} seconds ---")

一共用了8.353434562683105 seconds

复杂度分析

当数据正序时，执行效率最好，每次插入数据不移动前面的元素，时间复杂度为O(N)；当数据反序时，执行效率最低，每次排序都需要将元素后移，时间复杂度为O(N^2)。