数据结构之python实现插入排序(InsertionSort)
1 插入排序思想
认为第一个数有序,从后面取出一个数跟前面组成有序. **核心:**如何把后续数据插入相应的位置
-
通过构建有序序列,依次取出未排序序列的元素,并在已排序的序列中从后往前相比较,找到相应的位置并插入. 从后往前的扫描过程中,需要反复把已排序的元素向后挪位,为最新元素提供插入空间.
2 代码实现
def InsertionSort(li):
n = len(li)
# 前面数据已经有序,从后面取一个数,再跟前面组成有序
for j in range(1,n):
# 内部循环,从1取到n-1位置
# 游标从指定位置向前移动,如果小于前面,就交换
for i in range(j,0,-1):
if li[i] < li[i-1]:
li[i],li[i-1] = li[i-1],li[i]
else:
break
if __name__ == __main__:
li = [3,1,4,5,2]
ss = InsertionSort(li)
print(li)
3 复杂度分析
-
稳定性:稳定,如果数据不是相邻交换,则都是不稳定的 最坏时间复杂度 O(n^2) 最优时间复杂度 O(n) 循环最外层,内层每次都break
4 应用场景
如果数据大部分有序,插入排序效率最高
上一篇：
通过多线程提高代码的执行效率例子
下一篇：
二维数组的定义声明 java