Java - Insertion Sort

  public int[] sort(int[] array) {
    // Write your solution here
    if(array.length == 0 || array == null){
      return array;
  }
    // 从i = 1开始，此时认为array[0]有序
    for(int i = 1; i < array.length; i++){
      int j = i - 1;
      // 此次要插入的元素是global
      int global = array[i];
      while(j >= 0 && array[j] > global){// 此时所有的j（i前面的元素）都是排好序的
        // 排好序的元素里面如果有比global大的，就要往后挪一个
        array[j + 1] = array[j];
        j--;
      }  //  在j < 0 或者 array[j] <= global的时候跳出循环，即找到了此时array[i]应该在的位置
      // 因为有j--，所以此时j+1才是global应该在的位置
      array[j + 1] = global;
    }
    return array;
  }
}