排序总结之插入式排序(2)

/**
  * Knuth 提出的d=[d/3]+1，下取整。
  *
  * @param a
  */
 private void shellSort2(int[] a) {
  int d = a.length;
  int temp = 0;
  do {
   d=d/3+1;
   for (int x = 0; x < d; x++) {
    for (int i = x + d; i < a.length; i += d) {
     int j = i - d;
     temp = a[i];
     for (; j >= 0 && temp < a[j]; j -= d) {
      a[j + d] = a[j];
     }
     a[j + d] = temp;
    }
   }
  } while (d > 1);
 }
 /**
  * 折半插入排序是稳定的排序
  * 又称为二分插入排序，基本思想：设在数组中前i-1个元素是已经排好序的，
  * 在插入a[i]时，利用二分搜索的方法找到a[i]的位置插入。
  * @param a
  */
 private void binaryInsertSort(int[] a) {
  int temp = 0;
  int i, low, high, middle, k;
  for (i = 1; i < a.length; i++) {
   temp = a[i];
   low = 0;
   high = i - 1;
   while (low <= high) {
    middle = (low + high) / 2;
    if (temp < a[middle]) {
     high = middle - 1;
    } else
     low = middle + 1;
   }
   for (k = i - 1; k >= low; k--)
    a[k + 1] = a[k];// 成块移动空出插入位置
   a[low] = temp;
  }
 }
}