import java.util.Arrays;
/**
 * 插入排序
 *    选择未排序位置的数据，插入到数组已排序好的前半本部分
 *    遍历该部分，进行插入，然后将后继节点往后移一位
 */
public class InsertSort {
    public int[] insertSort(int[] arrays){
        if(null == arrays){
            throw new NullPointerException("arrays is null");
        }
        if(!(arrays.length>0)){
            return arrays;
        }
        int[] sortArrays = Arrays.copyOf(arrays, arrays.length);
        sort(sortArrays);
        return sortArrays;
    }
    private void sort(int[] arrays){
        int len = arrays.length;
        //i=0的位置默认是已经排序的，因为1个数组如何比较都是有序的
        //故i从1开始进行插入排序
        for(int i = 1;i<len;i++){
            //拿到需要插入的值
            int sortNum = arrays[i];
            //找到需要插入的位置
            int insertNum = i;
            for(int x = 0;x<=i;x++){
                if(arrays[x]>sortNum){
                    insertNum = x;
                    break;
                }
            }
            //将插入位置的值与后继节点向后移1位
            //为插入的值腾出位置
            for(int j = i;j>insertNum;j--){
                arrays[j] = arrays[j-1];
            }
            //进行值的插入
            arrays[insertNum] = sortNum;
        }
    }
    public void println(int [] a) {
        for(int x:a) {
            System.out.print(" "+x);
        }
        System.out.println("");
    }
    public static void main(String[] args) {
        int [] array = {9,3,4,12,8,5,6,2,0,11};
        InsertSort insertSort = new InsertSort();
        insertSort.println(array);
        insertSort.println(insertSort.insertSort(array));
    }
}

优化：二分插入排序