排序算法

插入排序

package sort;

public class InsertSort {
    static void insertSort(int[] array) {
      int j = 0;
//    Staright insertion Sort
      for(int i = 1; i < array.length; ++i) 
          if(array[i] < array[i - 1]) {
              int temp = array[i]; //复制为哨兵
              array[i] = array[i - 1];
              for( j = i - 2; j >=0 && temp < array[j]; --j) {
                  array[j + 1] = array[j]; //记录后移
              }
              array[j + 1] = temp; //插入到正确位置
          }
  }
}

二分插入排序

package sort;

public class BInsertSort {
    public static void binsertSort(int[] array) {
        int i = 0;
        for(i = 1; i < array.length; ++i) {
            int temp = array[i];
            int low = 0; int high = i -1;
            //折半插入有序插入的位置
            while(low <= high) {
                int m = (low + high)/2;
                if(temp < array[m]) //插入点在低半区
                    high = m -1;  
                else //插入点在高半区
                    low = m + 1;
            }
            for(int j = i - 1; j >= high + 1; --j)
                array[j + 1] = array[j]; //记录后移
            array[high + 1] = temp; //插入
        }
    }
}