分类导航

不忘初心mao 微信公众号：duhuo2017 《算法4》2.1 - 插入排序算法(Insertion Sort), Python实现

发布时间：2017年06月03日作者： IT网络文摘 (该文来自笔记，点击查看原文)

微信公众号：duhuo2017

排序算法列表电梯：

大家都打过牌吧，理牌的时候，每人手里一把牌，一般都会按由大到小顺序排好，每抓一个新牌（比如 5），都会找到4和6，把6往后挪一下，然后把5插到4和6之间。

插入排序算法的原理与理牌是一样的，在一组未排序或部分排序的物体中，将物体从左到右挨个比较，每比较一次，将物体从小到大排好，每次比较后，前面几个物体都是排好序了的，后面的物体插入到前面已排好的序列，以此类推直到全部排序完毕。

这里的关键是，在前面已经排好序的数组中插入后面的物体，所以叫做插入排序。

从一个 N 个数的数组或列表中，按从大到小或从小到大排序，排序的方法是：

1 确定是按从大到小还是从小到大排。（这里我们选择从小到大排序）

2 从小到大排的话，将第二个与第一个比较，如果小于第一个，则与第一个交换位置。反之不变。