algorithm - 壳排序和插入排序

Question

我有问题。我对 shell 排序和插入排序算法感到非常困惑。我们应该如何区分彼此？

Answer 1

Shell 排序是插入排序的通用版本。两种算法的基本原理相同。你有一个长度为n的排序序列，你将未排序的元素插入其中 - 你得到n+1 个元素的长排序序列。

区别如下：而插入排序仅适用于一个序列（最初是数组的第一个元素）并扩展它（使用下一个元素）。但是，shell 排序的增量是递减的，这意味着比较的元素之间存在间隙（最初是n/2）。因此，有n/2 个序列要使用插入排序进行排序。在每一步中，增量都会缩小（通常只除以2.2）并且序列的数量会减少。最后一步没有间隙，算法退化为简单的插入排序。

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

Answer 2

您可以将插入排序实现为连续元素的一系列比较和交换。这使其成为“稳定排序”。相反，Shell 排序比较和交换彼此相距较远的元素。这使它更快。

我想您的困惑来自这样一个事实，即 shell 排序可以实现为应用于不同数据子集的几种插入排序。请注意，这些子集由数据序列的不连续元素组成。

有关更多详细信息，请参阅 Wikipedia ;-)

Answer 3

插入排序是一种简单的就地 O(N^2) 排序。Shell 排序稍微复杂一些，也更难理解，大约在 O(N^(5/4)) 左右。检查链接以获取示例-应该很容易看出差异。