1. public static void main(String[] args) {
    2.         int[] arr = {1, 3, 5, 7, 8, 3, 4, 6, 0};
    3.         System.out.println(Arrays.toString(insertSort(arr)));
    4. }
    6.  /**
    7.      * 插入排序  对已经排好序的的元素进行 找出当前元素在其中的位置然后插入
    8.      *
    9.      * @param arr
    10.      * @return
    11.      */
    12.     public static int[] insertSort(int[] arr) {
    13.         if (arr != null && arr.length > 0) {
    14.             /**
    15.              * i = 0
    16.              *   j = 1 a[0] compareTo a[1] j--
    17.              *   j = 0 a[0] compareTo a[0]
    18.              *  result a[0]<a[1]
    19.              * i = 1
    20.              *   j = 2 a[1] compareTo a[2] j--
    21.              *   j = 1 a[0] compareTo a[1] j--
    22.              *   j = 0 a[0] compareTo a[0]
    23.              *  result a[0]<a[1]<a[2]
    24.              * i = 2
    25.              *   j = 3 a[2] compareTo a[3] j--
    26.              *   j = 2 a[1] compareTo a[2] j--
    27.              *   j = 1 a[0] compareTo a[1] j--
    28.              *   j = 0 a[0] compareTo a[0]
    29.              *  result a[0]<a[1]<a[2]<a[3]
    30.              * i = 3
    31.              *   j = 3 a[3] compareTo a[4] j--
    32.              *   j = 3 a[2] compareTo a[3] j--
    33.              *   j = 2 a[1] compareTo a[2] j--
    34.              *   j = 1 a[0] compareTo a[1] j--
    35.              *   j = 0 a[0] compareTo a[0]
    36.              *  result a[0]<a[1]<a[2]<a[3]<a[4]
    37.              *  ....
    38.              *
    39.              * i = arr.length - 1
    40.              */
    41.             for (int i = 0; i < arr.length -1; i++) {
    42.                 for (int j = i + 1; j >= 1 && j < arr.length; j--) {
    43.                     // 冒泡逻辑
    44.                     if (arr[j-1] > arr[j]) {
    45.                         int temp = arr[j-1];
    46.                         arr[j-1] = arr[j];
    47.                         arr[j] = temp;
    48.                     }
    49.                 }
    50.             }
    51.         }
    52.         return arr == null ? new int[]{} : arr;
    53.     }
    55.       public static int[] insertSort2(int[] arr){
    56.         // from 1 to 9 sorted
    57.         for(int i = 0;i<arr.length ;i++){
    58.             for(int j = i;j-1 >= 0  ;j--){
    59.                 if(arr[j] < arr[j-1]){
    60.                     int temp = arr[j];
    61.                     arr[j] = arr[j-1];
    62.                     arr[j-1] =temp;
    63.                 }else{
    64.                     break;
    65.                 }
    66.             }
    67.         }
    68.         return arr;
    69.     }
    70. // real
    71.  public static int[] insertSort3(int[] arr){
    72.         if(arr != null && arr.length > 0){
    73.             for(int i = 1;i<arr.length ;i++){
    74.                 int j = i -1;
    75.                 int cur = arr[i];
    76.                 for(;j>=0 && arr[j] > cur ;j--){
    77.                     arr[j+1] = arr[j];
    78.                 }
    79.                 arr[j+1] = cur;
    80.             }
    81.         }
    82.         return arr == null ? new int[]{} : arr;
    83.     }
    85. // 输出结果  [0, 1, 3, 3, 4, 5, 6, 7, 8]