【七类排序】之第二种：插入排序

写在前面的话

有人问，为什么如今我们的教材还要不厌其烦的教授这类效率慢的排序？ 我的体会是：为了格物致知。虽然我们也许以后不少基本的算法是我们用不着的， 我们能直接2分钟噼里啪啦把Qsort写完，或者边输入边直接建立Splay，Treap等高级数据结构，顺带把insert, delete, rotate等操作模块一并KO，我们甚至能直接调用模版库类。 但是，我们更需要做的是了解算法中每一步操作的精髓， 例如每一步循环的目的在哪？是如何承上启下的？ 以及如何每一个参数的范围是可以优化？ 时间复杂度常数项如何减小？ 哪两个步骤可以合并？ 在算法中，数量级的优化固然可喜， 但是难求，甚至数学上是不可行的。但是通过对算法的理解， 设计出小小的常数优化，甚至加几个判断得到的效果也常常是很显著的。 同样地， 创造设计优秀的算法， 也是要基于通透了解基本算法的基础上。 扯远了，回到正题。

注：若不特殊说明， 本文默认为递增排序。

插入排序（Insertion Sort）算法同样是最基础的排序方法，其效率之慢完全可以与冒泡排序媲美。但是根据鄙农印象，虽然同样为最基本的排序，似乎它在教材上的普及程度还是不及冒泡的。 令数组a[0..n-1], 该算法的思想概括为一句话就是：通过将第i个元素插入已经有序的前i-1中从而使得前i个元素有序。具体步骤为：

step 1： 初始状态下， a[0]自己是有序的， a[1..n-1]是无序的， 此时i=1。
step 2： 将a［ｉ］插入a[0..i-1]，使得a[0..i]有序。
step 3： i++, 重复步骤2， 直到i=n-1后， a[0..n-1]有序。

严格按照步骤写出代码的核心部分：

int i,j,k;
//由小到大枚举i
for (i=1; i<n; i++) {   
   //寻找到插入的地址j
   for (j=i-1; j>=0; j--)                         if (a[j]<a[ i ]) break;

   if (j!=i-1) {
       int temp=a[ i ];
       for (k=i-1; k>j; k--)
           a[k+1]=a[k];
       //插入正确的位置
        a[k+1]=temp;
   }
}

优化1： 将寻址和插入操作合并在一个循环内。
具体操作是，判断a[ i ]与a[i-1]， 若a[i-1]<a[ i ], 则前i个已然有序。 否则初始化指针j=i-1, 若a[j]>a[ j+1 ], 则往后移动一个单位， 也就是为了让a[ i ]沉下去，直到a[j]<a[j+1]则停止。代码如下：
int i,j;



for (i=1; i<n; i++)
    if (a[i-1]>a[ i ])  
    {
        int temp=a[ i ];
        //大于temp的元素后移一个单位
        for (j=i-1; j>=0 && a[j]>temp; j--)
             a[j+1] = a[j];
        a[j+1]=temp;
    }

优化2： 上面代码第二个循环是为了把大于temp的元素全部往后挪， 真麻烦.  还记得冒泡排序吗？ 冒泡排序是直接交换， 让a[ i ]像泡泡一样冒上去， 那这里的插入排序也用交换， 像石头一样沉下来。

最终版核心代码：

int i，j
for (i=1; i<n; i++)
    for (j=i-1; j>=0 && a[j]>a[j+1]; j--)
         swap(a[j],a[j+1]);

总结： 优化2这种形式的代码，是参照了冒泡排序的思想，只是方向相反罢了。至于别的实在没啥好说的， 插入排序很无聊。。如果有一天， 你突然需要排序一些数据， 而且数据量不大， 那么把插入排序写出来只要2分钟， 非常快， 因为核心部分就3行。。

1. overhead 小,当subarrary比较小(7~10)的时候， insert sort的效果是最好的.  qsort mergesort的base case一般是insertion sort.
2. 输入如果是partially-sorted， linear。 适合sort on streaming input.
3. insert sort 对branch prediction 很友好， 每个loop只有一次miss，即找到了正确的位置
4. stable

本來a[j+1] = a[j] 是一次賦值的，總共賦值次數是 n/2+n/4+...+1=n,

而swap() 要用到兩次賦值， 賦值次數是2n，所以其實優化2沒有優化1好

public ArrayList<Integer> insertionsort(ArrayList<Integer> a){
               
                for(int i=1;i < a.size();i++){
                        for(int j=i-1;j >= 0;j-- ){
                                if(a.get(j) > a.get(j+1))
                                        Collections.swap(a,j+1,j);
                        }
                }
                return a;
        }

优化2中  for (j=i-1; j>=0 && a[j]<a[j+1]; j--) 里面 应该把a[i] < a[j+1] 改成 a[j] > a[j+1]  否则是降序排序 而不是 升序排序