希尔排序和插入排序

Question

4

我有一个问题。我对希尔排序和插入排序算法非常困惑。我们应该如何区分它们？

- Rhokai

它们是完全不同的算法。 - sr01853

但它如何变得不同？请解释一下... - Rhokai

1

你读过维基百科的文章吗？它们对这两个算法有很好的解释。 - Jim Mischel

你可以询问自己是否能够区分不同的算法或实现。假设你真的想要比较实现，应该更好地关注这些算法在不同类型输入下的复杂度。 - Mihai8

3个回答

4

你可以将插入排序作为一系列相邻元素之间的比较和交换来实现。这使得它成为了“稳定排序”。而希尔排序则会比较和交换远离彼此的元素。这使得它更快。

我猜你的困惑来自于希尔排序可以被实现为对数据不同子集应用多个插入排序。请注意，这些子集由数据序列的非连续元素组成。

详见维基百科以获取更多详情 ;-）

- comocomocomocomo

4

插入排序是一种简单、原地的O(N^2)排序算法。相对而言，希尔排序更为复杂一些，难以理解，时间复杂度约为O(N^(5/4))。可以查看链接中的示例，很容易看出它们之间的区别。

- xpda

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- malejpavouk · Accepted Answer

希尔排序是插入排序的一般化版本。两种算法的基本原理相同。您有一个长度为n的排序序列，将未排序的元素插入其中，就可以得到一个长度为n+1的排序序列。

区别在于：插入排序仅使用一个序列（最初是数组的第一个元素）并扩展它（使用下一个元素）。

然而，希尔排序具有递减增量，这意味着比较的元素之间存在间隔（最初为n/2）。因此，需要使用插入排序对n/2个序列进行排序。每一步中，增量都会缩小（通常只需除以2.2），序列数也会减少。在最后一步中，没有间隔，算法退化为简单的插入排序。

由于递减增量，大型和小型元素被快速移动以纠正数组的一部分，然后在最后一步使用插入排序快速排序。这导致时间复杂度降低为O(n^(4/3))。