算法-插入排序

       今天看算法导论，觉得排序算法真的很重要，当然可能在应用层开发的时候根本体现不出来，因为sdk给我们封装好了sort方法，所以没有特殊需求的情况下，我们根本无需关心。但是好的算法基础决定你能走多远，所以我还是回头看一看。

 插入排序

插入排序，从第二个数开始和它之前的数做比较，如果比前边的小就换位，所以完成一个数比较时候前边的总是已经排好顺序的。

for(int i = 1;i<n;i++) {

     int key = i;

     int data = a[key];

     while(key > 0 && data < a[key -1]) {

           a[key] = a[key - 1];

           key --;

     }

     a[key] = data;

} 

换一种表现形式

for(int i = 1; i < n; i ++) {

    for(int j=i;j > 0 && a[j] < a[j-1];j--) {

          swap(a, j, j-1);

    }

}

时间复杂度 最坏情况 1 + 2 + ... + n-1 = n ^2/ 2  即O（n^2）

最好的情况O（n）已经有序

待续