算法简介

• 将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序
• 稳定排序
• 时间复杂度 O(n^2)

基本思想

将n个元素的数列分为已有序和无序两个部分，如下所示：
{{a1}，{a2，a3，a4，…，an}}
{{a1⑴，a2⑴}，{a3⑴，a4⑴ …，an⑴}}
…
{{a1(n-1），a2(n-1) ，…},{an(n-1)}}
每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。

java代码实现(整形数组)

• 实现类 Sort.java

public class Sort{
    public static void insertionSort(int[] a){  
        int i,j,key,n=a.length;
        for(j = 1;j < n;j++){
            key = a[j];
            i = j - 1;
            while(i >= 0 && a[i] > key){
                a[i + 1] = a[i];
                i--;
            }
            a[i + 1] = key; 
        }
    }
}

• 测试类 Test.java

public class Test{
    public static void main(String args[]){
        int a[] ={4,5,36,8,1,22};
        Sort.insertionSort(a);
        for(int i = 0; i < a.length; i++){
            System.out.println(a[i] + " ");
        }
    }
}

• 输出效果图

insertionsort.PNG