插入排序

原理

算法实现

/**
   * 将数组分为两部分，一部分是有序的，一部分是无序的，每次从无序的里面拿出一个，
   * 与有序数组进行比较, 默认第一个是有序的，所以遍历从1开始
   * @param arr
   */
public void sort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
      int cur = i;
      while (cur>=1 && arr[cur]<arr[cur-1]){
        ArrayUtil.swap(arr,cur-1,cur);
        cur--;
      }
    }
  }
public class ArrayUtil {
  public static void swap(int arr[], int left, int right){
    if(arr.length==0 || arr.length-1<left || arr.length-1<right){
      return;
    }
    int tmp = arr[left];
    arr[left] = arr[right];
    arr[right] = tmp;
  }
}

优化

优化交换的次数

  public void insertSort2(int[] arr){
    for (int i = 1; i <arr.length ; i++) {
      int temp = arr[i];
      int cur = i;
      while (cur>0 && arr[cur-1]>temp){
        //将比当前元素大的完后挪
        arr[cur] = arr[cur-1];
        cur--;
      }
      arr[cur] = temp;
    }

优化比较次数

public void insertSort3(int[] arr){
    for (int i = 1; i <arr.length ; i++) {
      //二分查找待插入的下标位置
      int insertIndex = searchFirstMaxIndex(arr, i);
      //挪动元素,挪动的元素范围为[insertIndex, i)
      int temp = arr[i];
      for (int j=i-1;j>=insertIndex;j--){
        arr[j+1] = arr[j];
      }
      arr[insertIndex] = temp;
    }
  }
/**
   * 查询第一个大于当前元素的数组下标
   * 查询的范围为[0,index)
   *
   * @param arr 原数组
   * @param index 待插入的元素下标
   * @return
   */
  public  int searchFirstMaxIndex(int[] arr,int index){
    if(arr == null || arr.length<=0) {
      return -1;
    }
  int begin = 0; int end = index;
    while (begin<end){
      int mid = begin +((end-begin)>>1);
      //如果>=mid，则在右边
      if(arr[mid]<=arr[index]){
        begin = mid+1;
      }else{
        end = mid;
      }
    }
    return end;
  }