带你读《图解算法小抄》十四、排序（22）

带你读《图解算法小抄》十四、排序（21）https://developer.aliyun.com/article/1348129?groupCode=tech_library

2）复杂度

3）参考资料

• 维基百科
  
• YouTube
  
• EfficientAlgorithms
  

10.希尔排序

希尔排序（Shellsort），也被称为 Shell 排序或 Shell 方法，是一种原地比较排序算法。它可以看作是交换排序（冒泡排序）或插入排序的推广。该方法从远离彼此的元素开始，对它们进行排序，然后逐渐减小要比较的元素之间的间隔。从远离彼此的元素开始，它可以更快地将一些错位的元素移动到正确的位置，而不只是简单地与最近的邻居交换。

1）希尔排序的工作原理

为了方便理解，我们以间隔为4的情况作为示例。将所有间隔为4位置的值组成一个虚拟子列表。这些值是 {35, 14}, {33, 19}, {42, 27} 和 {10, 44}。

我们比较每个子列表中的值，并在原始数组中进行交换（如果需要）。经过这一步，新数组应该如下所示：

然后，我们以间隔2进行排序，这个间隔会生成两个子列表：{14, 27, 35, 42} 和 {19, 10, 33, 44}。

我们在原始数组中比较并交换值（如果需要）。经过这一步，数组应该如下所示：

更新：下面的图片中存在一个错误，结果数组应该是 [14, 10, 27, 19, 35, 33, 42, 44]。

带你读《图解算法小抄》十四、排序（23）https://developer.aliyun.com/article/1348127?groupCode=tech_library