插入排序算法：每次处理一个数，把这个数插入到前面已经排好序的队列中。 arr[0,i) 是有序的队列，arr[i,n) 是无序的队列

    1. public class InsertSort {
    2.     public static void main(String[] args) {
    3.         Integer[] arr = {4, 6, 5, 3, 2, 1};
    4.         sort(arr);
    6.         for (int i = 0; i < arr.length; i++) {
    7.             System.out.println(arr[i]);
    8.         }
    10.         //验证选择排序算法的效率 算法复杂度是：O(n*n)
    11.         Integer[] dataSize = {10000, 100000};
    12.         for (Integer n : dataSize) {
    13.             Integer[] arrs = ArrayGenerator.generateRandomArray(n, n);
    14.             SortingHelper.sortTest("InsertSort", arrs);
    15.         }
    17.     }
    19.     public static <E extends Comparable<E>> void sort(E[] arr) {
    20.         //4 6 3 5 2 1 使用插入排序法进行排序
    21.         //3 4 6 5 2 1
    22.         //3 4 5 6 2 1
    23.         //2 3 4 5 6 1
    24.         //1 2 3 4 5 6
    25.         //当前位置前后比对 进行替换
    26.         for (int i = 0; i < arr.length; i++) {
    27.             for (int j = i; j > 0; j--) {
    28.                 if (arr[j].compareTo(arr[j - 1]) < 0) {
    29.                     swap(arr, j, j - 1);
    30.                 } else break;
    31.             }
    32.         }
    33.     }
    35.     private static <E extends Comparable<E>> void swap(E[] arr, int i, int j) {
    36.         E temp = arr[i];
    37.         arr[i] = arr[j];
    38.         arr[j] = temp;
    39.     }
    40. }

    减少数据替换操作：

    1.     public static <E extends Comparable<E>> void sort2(E[] arr) {
    2.         for (int i = 0; i < arr.length; i++) {
    3.             E temp = arr[i];
    4.             int j;
    5.             for (j = i; j > 0 && temp.compareTo(arr[j - 1]) < 0; j--) {
    6.                 arr[j] = arr[j - 1];
    7.             }
    8.             arr[j] = temp;
    9.         }
    10.     }