插入排序算法 #

1. 插入排序算法介绍
2. 插入排序算法原理
3. 插入排序算法的实现

收获 #

学完本节内容，可以初步理解并掌握插入排序算法。

插入排序算法介绍 #

插入排序(Insertion Sort)，也被称为直接插入排序，是一种常见的排序算法。
插入排序是将元素列表中未排序的数据依次插入到有序序列中。从元素列表的第一个数据开始(将第一个数据视为已排序序列)，按顺序将后面未排序的数据依次插入到前面已排序的序列中。对每一个未排序数据进行插入，是将该数据依次与相邻的前一个数据进行比较，如果顺序错误则交换位置，直到不需要交换则该数据插入完成。
插入排序的原理类似于玩扑克牌时，手动抓牌和排序，每抓一张新牌都按顺序插入到已有的牌中。

插入排序算法原理 #

插入排序的原理如下：

1. 将待排序列表的第一个元素当做已排序序列，第二个元素到最后一个元素当成未排序序列。
2. 取未排序序列中的第一个数据，插入到已排序序列中顺序正确的位置。将未排序的第一个数据与相邻的前一个数据(已排序序列的最后一个数)据进行比较，如果顺序错误则交换位置，交换位置后继续与相邻的前一个数据进行比较，直到不需要交换则插入完成。每次插入数据后，已排序序列都是排好序的。
3. 重复上一步，继续插入下一个数据。每进行一次插入，已排序序列的长度加1，未排序序列的长度减1，直到列表中的所有数据都插入到已排序序列了，则列表排序完成。

插入排序算法的实现 #

python实现代码如下：

a=[10,17,50,7,30,15,5,38,21]
n=len(a)
min_index=0
for i in range(1,n):
    value=a[i]#保存新的未排序的点的值
    j=i-1#已排序的最后一个数（前一个）
    while j>=0 and value<a[j]:
        min_index=j#当未排序的值<前一个值时，保留前一个值的index信息为局部最小位置
        a[min_index+1]=a[j]#该最小位置的后一个值为原来在该位置上的排序好的值（这样就实现了“插入”）
        j-=1#再在已排序好的数字中继续向前检索
        a[min_index]=value
print(a)

小结 #

理解并掌握插入排序算法的原理
掌握插入排序的代码实现

习题 #

1. 习题1：画出插入排序算法的流程图
2. 习题2：使用插入排序算法，对列表[10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]进行升序排列

–>