简单排序之插入排序

在大多数情况下，插入排序算法是基本的排序算法中最好的一种，在一般情况下，它比冒泡排序快一倍，比选择排序还要快一点，它经常被用到较复杂的排序算法的最后阶段，例如快速排序。

用插入排序为篮球队员排序

开始插入排序之前，把篮球队员随机顺序排成一排，从排序过程的中间开始，可以更好的理解插入排序，这时队列已经排好了一半。

局部有序

此时，在队伍的中间有一个作为标记的队员，可以把一件红色的毛巾扔到这个队员前面，在这个作为标记的队员左边的所有队员已经是局部有序的了，这就意味着这一部分人之间是按照顺序排列的；每个人比他左边的人都高，然而这些队员在队列中最终的位置还没有确定，因为当没有被排过序的队员要插入到他们中间的时候，他们的位置还要发生变动。注意，局部有序在冒泡排序和选择排序中是不会出现的，在这两个算法中，一组数据项在某个时刻是完全有序的；在插入排序中，一组数据仅仅是局部有序的。

被标记的队员

作为标记的队员，称为“被标记”的队员，他和他右边所有的队员都是未排过序的，下面将要做的是在局部有序组中的适当位置插入被标记的队员。然而要做到这一点，需要把部分已排序的队员右移来腾出空间。为了提供移动所需的空间，就先让被标记的队员出列(在程序中，把这个数据项存储在一个临时变量中)

现在移动已经排过序的队员来腾出空间。将局部有序中最高的队员移动到原来被标记队员所在的位置，次高的队员移动到原来最高的队员所在的位置，依次类推

这个移动过程什么时候结束呢？假设你和被标记的队员一起向队列的左端移动，在每个位置上，队员都向右移动一位，同时被标记的队员和下一个要移动的队员比较身高。当把最后一个比被标记的队员还高的队员移位之后，这个移动的过程就停止了，最后一次移位空出的位置，就是被标记队员应该插入的位置

现在，局部有序的部分里多了一个队员，而未排序的部分里少了一个队员。作为标记的毛巾向右移动一个位置，所以它仍然放在未排序部分的最左边的队员面前。重复这个过程，直到所有为排序的队员都被插入（插入排序由此得名）到局部有序队列中合适的位置

public void insertionSort(){
    int in,out;
    
    for(out=1;out<nElems;out++){
        long temp=a[out];
        in=out;
        while(in>0 && a[in-1]>temp){
            a[in]=a[in-1];
            --in;
        }
        a[in]=temp;
    }
}

在外层的for循环中，out变量从1开始，向右移动。他标记了未排序部分的最左端的数据，而在内层的while循环中，in变量从out变量开始，向左移动，直到temp变量小于in所致的数组数据项，或者它已经不能再往做移动为止。while循环的每一趟都向右移动了一个已排序的数据项

插入排序中的不变性

在每趟结束时，在将temp为止的项插入后，比outer变量下标号小的数据项都是局部有序的

插入排序的效率

复制的次数大致等于比较的次数。然而，一次复制与一次交换的时间耗费不同，所以相对于随机数据，这个算法比冒泡排序快一倍，比选择排序略好，在任意情况下，对于随机顺序的数据进行插入排序也需要O(N²)的时间级。

对于已经有序或者基本有序的数据来说，插入排序要好得多，然而对于逆序排列的数据，每次比较和移动都会执行，所以插入排序不比冒泡排序快

几种简单排序之间的比较

• 一般情况下几乎不太使用冒泡排序算法，只有当数据量很小的时候它有些应用价值
• 选择排序虽然把交换次数降到最低，但比较的次数仍然很大，当数据量很小，并且交换数据相对于比较数据更加耗时的情况下，可以使用选择排序
• 在大多数情况下，假设当数据量比较小或基本上有序时，插入排序算法是三种简单排序算法中最好的选择，对于更大数据的排序来说，快速排序通常是最快的方法