说明：本代码由b站网友：万众烟火不及你 编写

仅供学习参考，转载请标明出处

代码难免存在bug，请网友海涵，以下为代码部分

InsertSort.java :

package InsertSort;

//插入排序
public class InsertSort {
    public static void main(String[] args) {
        int[] a = {10,8,11,7,4,12,9,6,5,3};
        System.out.print("排序前的数组：");
        printArray(a);
        System.out.print("排序后的数组：");
        printArray(insertionSort(a));
    }

    static int[] insertionSort(int[] arr){
        int n = arr.length;
        for (int i = 1; i < n; i++){  //为什么从1开始？因为第0个元素本身就是有序的
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key){  //前一个数大于后一个数，则交换
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
        return arr;
    }
    //打印数组
    static void printArray(int[] arr){
        for (int j : arr) {
            System.out.print(j + " ");
        }
        System.out.println();
    }
}

测试用例：

-----以下为输出-----
排序前的数组：10 8 11 7 4 12 9 6 5 3 
排序后的数组：3 4 5 6 7 8 9 10 11 12