直接插入排序

public static void insertionSort(int[] arr){
    for( int i = 1; i < arr.length; i++ ) {
        int temp = arr[i];    // 取出下一个元素，在已经排序的元素序列中从后向前扫描
        for( int j = i; j >= 0; j-- ) {
            if( j > 0 && arr[j-1] > temp ) {
                arr[j] = arr[j-1];    // 如果该元素（已排序）大于取出的元素temp，将该元素移到下一位置
                System.out.println("Temping:  " + Arrays.toString(arr));
            } else {
                // 将新元素插入到该位置后
                arr[j] = temp;
                System.out.println("Sorting:  " + Arrays.toString(arr));
                break;
            }
        }
    }
}

// 交换次数较多的实现
public static void insertionSort(int[] arr){
    for( int i=0; i<arr.length-1; i++ ) {
        for( int j=i+1; j>0; j-- ) {
            if( arr[j-1] <= arr[j] )
                break;
            int temp = arr[j];      //交换操作
            arr[j] = arr[j-1];
            arr[j-1] = temp;
            System.out.println("Sorting:  " + Arrays.toString(arr));
        }
    }
}


//JDK直接插入排序
public static void insertSort(int[] a,int left,int right){
    for (int i = left, j = i; i < right; j = ++i) {
        int ai = a[i + 1];
        while (ai < a[j]) {
            a[j + 1] = a[j];
            if (j-- == left) {
                break;
            }
        }
        a[j + 1] = ai;
    }
}