希尔排序

希尔排序 - 第一个突破O(\(n^2\))的排序算法 （插入排序算法类）

希尔排序（shell sort）是基于直接插入排序的改进版，基本思想是将原有的序列分割成若干子序列，子序列内分别进行插入排序，当整个序列基本有序是，对全体记录进行直接插入排序。 也叫缩小增量排序。

基本原理

shellsort

代码实现

public static void shellSort(int[] input) {

  int length = input.length;

  // eg length =7, gap: 3, 1
  for (int gap = length / 2; gap > 0; gap /= 2) {
    System.out.println("Current gap is :" + gap);

    for (int i = gap; i < length; i++) {
      int tmp = input[i];
      int j = i - gap;
      while (j >= 0 && tmp < input[j]) {
        input[j + gap] = input[j];
        j -= gap;
      }
      input[j + gap] = tmp;
    }

  }
}

如何选择Gap ?

https://en.wikipedia.org/wiki/Shellsort#Gap_sequences