希尔排序

一、什么是希尔排序？

• 希尔排序是一种基于插入排序进行了优化后的排序算法
• 希尔排序比普通插入排序更适用于大规模数组排序

二、为什么要用希尔排序？

普通的插入排序存在一个问题：

• 对于大规模乱序数组排序很慢

而它这么慢的原因是：

• 插入排序只是交换相邻元素，因此元素只能一点点从一端移动到另一端

比如说，数组 [7, 2, 3, 5, 6, 4, 1]，插入排序只能一点点地将 1 移动到最前面。

希尔排序为了加快这种情况的排序速度，对插入排序进行了优化：

• 对数组元素按照指定间隔进行跳跃式的分组
• 对分组内进行局部排序，交换不相邻的元素
• 最终用插入排序将局部有序数组进行排序

比如说，数组 [7, 2, 3, 5, 6, 4, 1]。

希尔排序会将其划分为多个组，假设按照间隔为 3 分组，可分成 3 组：

   _______________________________________________
  |                       |                       |
  v                       v                       v
 ___     ___     ___     ___     ___     ___     ___
| 7 |   | 2 |   | 3 |   | 5 |   | 6 |   | 4 |   | 1 |

           _______________________
          |                       |
          v                       v
 ___     ___     ___     ___     ___     ___     ___
| 7 |   | 2 |   | 3 |   | 5 |   | 6 |   | 4 |   | 1 |

                   _______________________
                  |                       |
                  v                       v
 ___     ___     ___     ___     ___     ___     ___
| 7 |   | 2 |   | 3 |   | 5 |   | 6 |   | 4 |   | 1 |

然后分别对每个组内进行排序：

               [7, 5, 1] --> [1, 5, 7]

   _______________________________________________
  |                       |                       |
  v                       v                       v
 ___     ___     ___     ___     ___     ___     ___
| 1 |   | 2 |   | 3 |   | 5 |   | 6 |   | 4 |   | 7 |

              [2, 6] --> [2, 6]

           _______________________
          |                       |
          v                       v
 ___     ___     ___     ___     ___     ___     ___
| 1 |   | 2 |   | 3 |   | 5 |   | 6 |   | 4 |   | 7 |

                      [3, 4] --> [3, 4]

                   _______________________
                  |                       |
                  v                       v
 ___     ___     ___     ___     ___     ___     ___
| 1 |   | 2 |   | 3 |   | 5 |   | 6 |   | 4 |   | 7 |

可以看到，1 已经直接移动到最前面了，从一端移动到另一端的速度很快。

而且，在局部有序的情况下，整个数组看起来也基本是有序的了。

希尔排序就是采用间隔分组排序的方式，来优化对大规模的数组排序。

三、如何实现希尔排序？

希尔排序的基本思想是按照间隔进行跳跃式分组，并对组内进行排序。

其排序过程是这样：

1. 按照间隔 h 对数组进行跳跃式分组
2. 对每个分组内的元素进行排序
3. 缩小间隔 h，重新回到第 1 步，直到 h = 1 为止

这里面有 2 个核心的点：

• 分组内的排序
• 间隔 h 的选择和缩小

当间隔 h = 1 时，其实就是普通的插入排序了。

3.1 分组内排序

一般来说，希尔排序的实现中，分组内排序采用的是插入排序。

比如对这个分组进行插入排序：

   _______________________________________________
  |                       |                       |
  v                       v                       v
 ___     ___     ___     ___     ___     ___     ___
| 7 |   | 2 |   | 3 |   | 5 |   | 6 |   | 4 |   | 1 |

   _______________________________________________
  |                       |                       |
  v                       v                       v
 ___     ___     ___     ___     ___     ___     ___
| 5 |   | 2 |   | 3 |   | 7 |   | 6 |   | 4 |   | 1 |           -- (5 插到 7 前)

   _______________________________________________
  |                       |                       |
  v                       v                       v
 ___     ___     ___     ___     ___     ___     ___
| 1 |   | 2 |   | 3 |   | 5 |   | 6 |   | 4 |   | 7 |           -- (1 插到 5 前)

所以说希尔排序本质就是插入排序，只是插入的方式有点不同。

插入排序是相邻元素之间的交换，而希尔排序是跳跃式的交换。

3.2 增量序列

希尔排序中的间隔 h 变化序列，一般称为增量序列。

比如说，开始间隔 h = n / 2，后面以 h = h / 2 缩小增量：

n/2 n/4 n/8 ... 1

那么这样的一个序列，就称为增量序列。

• 目前来说，希尔排序的增量序列的选择还没有最优的方案

因为增量序列的选择和证明还是一个数学难题。

除了上面取中的增量序列，在《算法》一书中还给出了 2 种增量序列：

1, 4, 13, 40, 121, 364 ... (h = 3 * h + 1)

1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929, 16001, 36289, 64769, 146305, 260609

希尔排序的性能会受到增量序列的影响，但是目前暂时没有办法证明哪个增量序列是最优的。

四、算法分析

4.1 时间复杂度

• 目前尚未能准确算出来复杂度
• 只能知道大概范围：nlogn < O < n^2

4.2 空间复杂度

• 空间复杂度：O(1)
• 原地算法

4.3 稳定性

• 非稳定排序算法

总结

• 希尔排序是一种基于插入排序进行了优化后的排序算法
• 希尔排序比普通插入排序更适用于大规模数组排序
• 希尔排序的关键点包括增量序列的选择和分组内排序
• 目前还没有找到最优的增量序列
• 暂时无法证明希尔排序的时间复杂度

参考

https://www.cnblogs.com/chengxiao/p/6104371.html

附录

/**
 * 希尔排序
 * <p>
 * 时间复杂度：暂时无法分析，但是达不到 O(n^2)
 * <p>
 * 空间复杂度：O(1)
 * <p>
 * 稳定性：不稳定
 */
public void shellSort(int[] arr) {
    int n = arr.length;

    // 递增序列：1, 4, 13, 40, 121, ...
    int h = 1;
    while (h < n / 3) {
        h = 3 * h + 1;
    }

    // 增量序列倒序递减至 1
    while (h >= 1) {
        // 局部插入排序
        for (int i = h; i < n; i++) {
            int x = arr[i];
            int j = i;
            for (; j >= h && x < arr[j - h]; j -= h) {
                arr[j] = arr[j - h];
            }
            arr[j] = x;
        }
        // 递减 h 间隔
        h /= 3;
    }
}