插入排序时间复杂度O(n^2)
    对于有序数组时间复杂度为O(n)

    1. public static <E extends Comparable<E>> void sort(E[] nums) {
    2.         int length = nums.length;
    3.         for (int i = 0; i < length; i++) {
    4.             int j = i;
    5.             //将nums[i]插入到合适的位置
    6.             while (j - 1 >= 0) {
    7.                 if (nums[j].compareTo(nums[j - 1]) < 0) {
    8.                     E num = nums[j - 1];
    9.                     nums[j - 1] = nums[j];
    10.                     nums[j] = num;
    11.                 }
    12.                 j--;
    13.             }
    14.         }
    15.         System.out.println(Arrays.toString(nums));
    16.     }
    18. public static <E extends Comparable<E>> void sort2(E[] nums) {
    19.         int length = nums.length;
    20.         for (int i = 0; i < length; i++) {
    21.             //将nums[i]插入到合适的位置
    22.             //第一种写法
    23.             for (int j = i; j - 1 >= 0; j--) {
    24.                 if (nums[j].compareTo(nums[j - 1]) < 0) {
    25.                     E num = nums[j - 1];
    26.                     nums[j - 1] = nums[j];
    27.                     nums[j] = num;
    28.                 }
    29.             }
    30.             //第二种写法
    31.             for (int j = i; j - 1 >= 0 && nums[j].compareTo(nums[j - 1]) < 0; j--) {
    32.                 E num = nums[j - 1];
    33.                 nums[j - 1] = nums[j];
    34.                 nums[j] = num;
    35.             }
    37.         }
    38.         System.out.println(Arrays.toString(nums));
    39.     }
    41.  public static <E extends Comparable<E>> void sort3(E[] arr) {
    42.         for (int i = arr.length - 1; i >= 0; i--) {
    43.             // 将 arr[i] 插入到合适的位置
    44.             E t = arr[i];
    45.             int j;
    46.             for (j = i; j + 1 < arr.length && t.compareTo(arr[j + 1]) > 0; j++) {
    47.                 arr[j] = arr[j + 1];
    48.             }
    49.             arr[j] = t;
    50.         }
    51.     }
    53.  /**
    54.      * 优化后的排序方法
    55.      * <p>
    56.      * 前面方法都是采用比较一次给相关元素赋值一次,优化后采用位置向后平滑设置值,最后赋值给正在寻找位置插入的值
    57.      *
    58.      * @param arr 数组
    59.      * @param <E> E
    60.      */
    61.     public static <E extends Comparable<E>> void sort4(E[] arr) {
    62.         for (int i = 0; i < arr.length; i++) {
    63.             E t = arr[i];
    64.             int j;
    65.             for (j = i; j - 1 >= 0 && t.compareTo(arr[j - 1]) < 0; j--) {
    66.                 arr[j] = arr[j - 1];
    67.             }
    68.             arr[j] = t;
    69.         }
    70.         System.out.println(Arrays.toString(arr));
    71.     }
    73. public static void main(String[] args) {
    74.         Integer[] nums = {5, 2, 4, 6, 1, 3};
    75.         sort(nums);
    76.         sort2(nums);
    77.         sort3(nums);
    78.         sort4(nums);
    79.     }

    go实现:

    1. func main() {
    2.     insertionSort([]int{5, 2, 4, 6, 1, 3})
    3. }
    5. func insertionSort(arr []int) {
    6.     for i := 0; i < len(arr); i++ {
    7.         for j := i; j-1 >= 0 && arr[j] < arr[j-1]; j-- {
    8.             a := arr[j-1]
    9.             arr[j-1] = arr[j]
    10.             arr[j] = a
    11.         }
    12.     }
    13.     fmt.Println(arr)
    14. }

    项目demo