插入排序

package 排序.插入排序;

public class InsertSort {

    public  static void  insertSort(int[] arr){
        if ( arr == null || arr.length <2 ){
            return;
        }
//            0~0  :已经完成
//            0~1
//            0~2
//            0~3
        int N = arr.length;
        for (int end = 1; end < N; end++) {
            int newNumIndex = end;   //每一次刚开始的新来的数，在end位置上,
               while (newNumIndex-1>=0 && arr[newNumIndex-1]>arr[newNumIndex]){
                   exchange(arr,newNumIndex-1,newNumIndex);//  一开始去看end-1位置。左边有数，而且比自己大
                   newNumIndex--;
            }
        }
    }

    public  static   void  exchange(int[] arr,int i,int j){
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;

    }
    public  static void printArray(int[] arr){
        for (int i = 0; i <arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }

    public static void main(String[] args) {
        int arr[] = {7,1,3,5,1,6,8,1,3,5,7,5,6};
        System.out.println("排序前");
        printArray(arr);
        insertSort(arr);
        System.out.println("\n");
        System.out.println("排序后");
        printArray(arr);

    }
}

插入排序就是，不断地从 0~0 0~1 0~2 0~3 排好序，所以最外面的排序就是：

for (int end = 1; end < N; end++) {
    ......
    }

优化后：

public  static void  insertSort2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int N = arr.length;
        for (int end = 1;end < N;end ++){
            // pre  :新数的前一个位置
            for (int pre = end-1; pre>=0 && arr[pre] >arr[pre+1];pre-- ){
                exchange(arr,pre,pre-1);
            }
        }
    }