python实现插入排序(InsertSort)
2020-12-07 本文已影响0人
阿旭123
python实现【插入排序】
算法原理及介绍
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在
已排序序列中从后向前扫描，找到相应位置并插入。
算法过程描述
具体算法描述如下：
-
从第一个元素开始，该元素可以认为已经被排序；
-
取出下一个元素，在已经排序的元素序列中从后向前扫描；
-
如果该元素（已排序）大于新元素，将该元素移到下一位置；
-
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
-
将新元素插入到该位置后；
-
重复步骤2~5。
注意: 在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
算法排序图解如下
插入.gif
python实现代码
def insertSort(arr):
n = len(arr)
for i in range(1,n):
preIndex = i - 1
current = arr[i] # 保存当前需要进行插入元素值
while preIndex >= 0 and arr[preIndex] > current:
# 在已排序数组中找到cunrent值能够放下的相应索引位置
arr[preIndex + 1] = arr[preIndex] # 元素后移,为需要插入的元素腾位置
preIndex -= 1
arr[preIndex + 1] = current
return arr
如果喜欢作者，欢迎点赞、收藏及关注，谢谢！
点击下面相应的链接即可查看各个算法的详细介绍及python实现方法：
