排序算法-插入排序

一、排序算法原理

　　将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。那么也就是说，每次插入一个数都要对原来排序好的那部分序列进行重新的排序。

二、时间复杂度（n²）

　　 1 + 2 + 3 + (n-1) = (n²-n)/2

三、代码实现

　　3.1 利用for循环实现

 1 from Common.CreateData import createData
 2 from Common.Swap import swap
 3 
 4 
 5 def insertionSort(lyst):
 6     for i in range(1, len(lyst)):
 7         for j in range(i, 0, -1):
 8             if lyst[j] < lyst[j - 1]:
 9                 # 数据交换，和swap(lyst, j, j - 1) 等价
10                 lyst[j], lyst[j - 1] = lyst[j - 1], lyst[j]
11                 print(lyst)
12 
13 
14 insertionSort(createData())

　　3.2 利用while实现

 1 from Common.CreateData import createData
 2 
 3 
 4 def insertSort(lyst):
 5     i = 1
 6     while i < len(lyst):
 7         insertionTemp = lyst[i]
 8         j = i - 1
 9         while j >= 0:
10             if insertionTemp < lyst[j]:
11                 lyst[j + 1] = lyst[j]
12                 j -= 1
13                 print(lyst)
14             else:
15                 break
16         lyst[j + 1] = insertionTemp
17         i += 1
18     print(lyst)
19 
20 
21 insertSort(createData())

四、运行过程

　　4.1 for循环：

　　4.2 while：