插入排序 优化插入排序

package Code01;

import java.util.Scanner;

public class factorial {

//    求1~N的阶乘之和   1！+2！+3+ ... + N!
    public  static void fac_one(int m){
        int rec = 1;
        int sum = 0;
        for(int j=1;j<=m;j++){
            rec = rec*j;
            sum += rec;
        }
        System.out.print(sum);
    }

//    交换函数
    public static void swap(int[] arr, int a, int b){
        int tmp = arr[b];
        arr[b] = arr[a];
        arr[a] = tmp;
    }

//    插入排序
    public static void insertSort(int[] arr){
        if(arr==null || arr.length<2){
            return;
        }
        //0~0 完成
        //0~1
        //0~2
        //0~3
        //0~n-1
        int N = arr.length;
        for(int end=1;end < N;end++){
            int newNumIndex = end;
            while(newNumIndex-1 >=0 && arr[newNumIndex-1] > arr[newNumIndex]){
                swap(arr, newNumIndex-1, newNumIndex);
                newNumIndex--;
            }
        }
    }

//    优化插入排序
    public static void optinsertSort(int[] arr){
        if(arr==null || arr.length<2){
            return;
        }

        int N = arr.length;
        for(int end=0; end<N; end++){
            for(int pre = end-1; pre>=0 && arr[pre]>arr[pre+1]; pre-- ){
                swap(arr, pre, pre+1);
            }
        }
    }


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

    public static void main(String[] args){
        int[] arr = {7,1,3,5,1,6,8,1,3,5,7,5,6};
        printArray(arr);
        insertSort(arr);
        printArray(arr);
        optinsertSort(arr);
        printArray(arr);

    }
}