希尔排序

原理

• 插入排序的一种改进版本

• 步骤

  • 将待排序序列分为若干子序列（每个子序列的元素在原始数组中间距相同）
  • 对这些子序列进行插入排序
  • 减小每个子序列中元素之间的间距，重复上述过程直至间距减少为1

    性质

• 稳定性 ： 不稳定

• 时间复杂度
  • 最优：
  • 平均和最坏与间距序列的选取有关，已知最好的最坏时间复杂度为

    代码

    public void shell_sort(int[] a) {
    int h = 1;
    while (h < a.length / 3) {
       h = 3 * h + 1;
    }
    while (h >= 1) {
       for (int i = h; i < a.length; i++) {
           int key = a[i];
           int j = i - h;
           while (j >= 0 && a[j] > key) {
               a[j + h] = a[j];
               j = j - h;
           }
           a[j + h] = key;
       }
       h = h / 3;
    }
    }