把一个新的元素插入已排好序的数组形成一个新的已排好序的数组 从第一个元素开始，取下一个元素比较后实现排序，形成新的数组， 再取第三个元素与该数组比较， 比较时从该数组的最后一位开始比较， 若新元素比与其比较的元素小，则将该比较的元素后移以为， 直到新元素比该数组左边找到其应该插入的位置。（转自七月回来继续发博客）
平均时间复杂度：O(n^2)
public static void insertionSort(int[] arr) { // 从第二个数开始，第一个数默认有序 for (int i = 1; i < arr.length; i++) { // 记录要插入的数据 int temp = arr[i]; int j = i; // 从有序记录的右边开始比较，找到比他小的，并插入 while (j > 0 && temp < arr[j - 1]) { arr[j] = arr[j - 1]; j--; } arr[j] = temp; } }