下载掌阅APP，畅读海量书库
立即打开
插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
把 n 个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有 n -1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复 n -1次可完成排序过程。
例如，有一组初始化数组[8，2，5，9，7]，把数组中的数据分成两个区域，已排序区域和未排序区域，初始化的时候所有的数据都处在未排序区域中，已排序区域是空的。
（1）第一轮排序，从未排序区域中随机拿出一个数字，既然是随机，那么我们就获取第一个，然后插入到已排序区域中，如果已排序区域是空，那么就不做比较，默认自身已经是有序的了。
（2）第二轮排序，继续从未排序区域中拿出一个数，插入到已排序区域中，这个时候要遍历已排序区域中的数字遍历做比较，比大比小取决于我们是想升序排还是想倒序排，这里按升序排。
（3）第三轮排序，排5。
（4）第四轮排序，排9。
（5）第五轮排序，排7。
（6）排序结束。
【例3-9】 利用插入排序对序列[11，11，22，33，33，36，39，44，55，66，69，77，88，99]进行排序。
运行程序，输出如下：
排序后的结果为：
[11,11,22,33,33,36,39,44,55,66,69,77,88,99]
