### **直接插入排序算法思想** 把待排序的纪录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的纪录插入完为止，得到一个新的有序序列。 插入排序基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。 > 直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。 设无序数组为a\[0…n-1\]。 * 1.初始时，a\[0\]自成1个有序区，无序区为a\[1..n-1\]。 * 2.令i=1,将a\[i\]插入当前的有序区a\[0…i-1\]中形成a\[0…i\]的有序区间。 * 3.i++并重复第二步直到i==n-1，排序完成。 * * * ### **一趟直接插入排序方法** 具体做法： 将待插入记录 a\[i\]的关键字从右向左依次与有序区中记录 a[j]的关键字进行比较： * 1.若 a\[j\]的关键字大于 a\[i\]的关键字，则将 a\[j\]后移一个位置； * 2.若 a\[j\]的关键字小于或等于 a\[i\]的关键字，则查找过程结束，j+1 即为 a\[i\]的插入位置。 关键字比a\[i\]的关键字大的记录均已后移，所以 j+1 的位置已经腾空，只要将 a\[i\] 直接插入此位置即可完成一趟直接插入排序。 例如待排序数组a\[0\]=8,a\[1\]=5,a\[2\]=10,a\[3\]=12,a\[4\]=7,a\[5\]=6 第一趟：a\[0\]=8，有序,a\[1...5\]无序。 第二趟：temp=5，a\[1\]=5 < a\[0\]=8, 8往后移一位，a\[1\]=8,a\[0\]=5,a\[0...1\]有序,a\[2...5\]无序。 第三、四趟：a\[2\]=10 > a\[1\]=8,a\[3\]=12 > a\[2\]=10，有序无须移动，a\[4...5\]无序。 第五趟：temp=7，a\[4\]=7 < a\[3\]=12,12往后移一位，a\[4\]=12，依次类推...直到a\[0\]=5 < temp，即a\[1\]=7。 第六趟类比第五趟，可以得到6插入位置为a\[1\]=6。排序完成。 * * * *直接插入排序算法时间复杂度：O(n^2)；空间复杂度：O(1)。直接插入排序是稳定的排序方法。*