排序算法之插入排序

排序分为内部排序和外部排序。内部排序指的是能够在主内存中完成的算法排序；外部排序指的是必须在磁盘或者磁带上完成的排序。下面介绍内部排序系列。

插入排序

插入排序的基本思想是每一步将一个待排序的数据根据关键的值得比较，将这个数据插入到有序的数据列中。

插入排序的特点：

1. 待插入的序列是一个有序的数据列；
2. 适用于少量数据的排序；
3. 时间复杂度为O(n^2);

插入排序的java代码实现：

**
 * 插入排序
 */
public class InsertSort  {
    public static <AnyType extends Comparable<? super AnyType>> void insert(AnyType[] a){
        int j;
        for(int i=1;i<a.length;++i){
            AnyType tmp = a[i];
            for(j=i;j>0&&tmp.compareTo(a[j-1])<0;j--){
                a[j] = a[j - 1];
            }
            a[j] = tmp;
     
        }
    }
}

从代码可以看出每插入一个数据都需要和前面的数据相比较，然后才能确定这个数据的位置，因此时间复杂度为O(n^2)。