十大排序算法（三）--- 插入排序

插入排序的思想是将当前的元素插入到一个已经排序好的有序数组中的适当位置，从而保证插入后数组依然有序。插入排序的最坏的时间复杂度是O(n^2), 最好的情况是O(n)，具体时间复杂度度取决于原始待排序数组的有序程度，如果待排序数组完全逆序则时间复杂度就是O(n^2), 如果待排序数组完全有序，那么时间复杂度就是O(n)。

假设我们要对数组A[1,2,0,2,3,7,5]进行排序，下面通过图例展示排序的过程：

由排序过程可以看出，插入排序需要两层循环，上图中未缩进的展示行为外层循环，缩进的展示行为内层循环。整个排序过程比较简单。下面是python的代码实现，有兴趣的读者也可以尝试其它语言实现一下。

A = [1,2,0,2,3,7,5]

def insertion_sorting(data):

num = len(data)

for i in range(1, num):

markIndex = i

for j in range(i-1, -1, -1):

if data[markIndex] < data[j]:

data[markIndex], data[j] = data[j], data[markIndex]

markIndex = j

else: break

return data

def main():

#Ascending

print(insertion_sorting(A))

if __name__=='__main__':

main()

将上面的代码保存到一个文本文件，后缀名修改为.py。可以用python解释器执行一下，会输出如下结果：

可以看到，排序正确。