10.3.2　插入排序

10.3.2　插入排序

插入排序（Insertion Sort）每一步将待排序元素插入前面已经排序的有序序列中，一直到所有的元素都被插入为止。

根据插入排序的实现原理，对如图10.5所示的无序状态的元素，进行插入排序举例：

第一步，把9插入12前面，变成9、12、2、8、23、7、16；

第二步，把2插入9前面，变成2、9、12、8、23、7、16；

第三步，把8插入9前面，变成2、8、9、12、23、7、16；

第四步，把23插入12后面（其实不用移动位置），第三步排成后序列不变；

第五步，把7插入8前面，变成2、7、8、9、12、23、16；(https://www.daowen.com)

第六步，把16插入23前面，变成2、7、8、9、12、16、23，排序完成。

图10.5　无序状态的元素队列

代码文件：10_3_2_InsertionSort.py

代码执行结果如下：