排序算法(3)-插入排序

原理：把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。

---

排序过程:

                有一组数  {5 , 9 , 2 , 6 , 4 , 1 , 8 , 7}

                 把上述数组看为有序数组和无序数组,那这组数据中有序数组是什么呢？何不把数组的第一个数 {5}看成一个有序 其余的{9  , 2  , 6  , 4  , 8  , 7}作为无序部分。

                有序部分 ： {5}

                无序部分 :   {9 , 2 , 6 , 4 , 1 ,8 , 7}

                第二次插入:  从无序部分拿出 9  ,   5>  9?  否   不需要插入到有序。

                 此时有序无序无变化

                 第三次插入:从无序部分拿出 2 ， 5 > 2 ? 是    插入到有序

                  有序部分:{2,5}

                   无序部分:{9,6,4,1,8,7}

                  第四次插入:从无序部分拿出6， 5 >6 ？否,再比较  2 >6 ? 否 ,有序无序无变化

                  第五次插入:从无序部分难处4， 5 >4 ? 是,将 4 插入到 有序{2,4,5} 再比较  2 > 4？否,不需要调换位置

。。。。。

。。。。。

---

代码实现

---

时间复杂度:插入排序的时间复杂度分析。在最坏情况下，数组完全逆序，插入第2个元素时要考察前1个元素，插入第3个元素时，要考虑前2个元素，……，插入第N个元素，要考虑前N - 1个元素。因此，最坏情况下的比较次数是1 + 2 + 3 + ... + (N - 1)，等差数列求和，结果为N^2 / 2，所以最坏情况下的复杂度为O(N^2)。

最好情况下，数组已经是有序的，每插入一个元素，只需要考查前一个元素，因此最好情况下，插入排序的时间复杂度为O(N)。