Python中排序算法之插入排序
1 插入排序算法原理
插入排序算法与《Python中排序算法之选择排序》中提到的选择排序算法类似，也是将要排序的数列分为两个子数列（红色框数列和绿色框数列），不同之处在于插入排序算法从绿色框子数列中逐个选择数字，之后按照升序或者降序插入到红色框子数列中。而选择排序是在绿色框子数列中选择最小或最大数字，之后将该数字放到红色框子序列的尾部。
插入排序算法很像现实中玩扑克牌时，一边抓牌（绿色框子数列），一边理牌（红色框子数列）的过程，抓一张牌就把它插入到应有的位置。
2 插入排序的手动实现
假设要排序的数列中的数字是“3，8，5，9，6”。首先，从绿色框子数列中逐个选择数字，第一个数字是“3”，将其放入到红色框中，如图1所示。
图1 第一次排序
接下来，选择绿色框中子数列的数字“8”，按照升序（从小到大）将其插入到红色框中的子数列中，如图2所示。
图2 第二次排序
然后，选择绿色框中子数列的数字“5”，按照升序（从小到大）将其插入到红色框中的子数列中，如图3所示。
图3 第三次排序
按照相同的方法，依次选择绿色框中子数列的数字“5”和“6”，按照升序（从小到大）将其插入到红色框中的子数列中，如图4所示。
图4 剩余的排序
注意1 使用插入排序算法对n个数字进行排序时，需要排n-1次。
3 插入排序的代码实现
通过图5所示的代码，实现插入升序（从小到大）的排序算法。
图5 插入排序的代码实现
其中，第1行为要排序的数列；第2行的for循环表示排序的次数；第3行中的key表示从绿色框子序列中逐个取出的数；第3行j表示取出的数字要插入到红色框子序列的位置；第5-8行代码通过while循环，找到要插入的红色框子序列的位置，并把key插入到j表示的位置处，完成插入排序。程序运行的效果如图6所示。
图6 程序运行效果
相关链接1 使用插入排序算法进行降序（从大到小）的代码，只需将图5第5行中的“>”改为“<”即可。