我遇到了一个问题。我对 shell 排序和插入排序算法感到很困惑。我们应该如何区分？
最佳答案
Shell sort是 Insertion sort 的通用版本.两种算法的基本原理相同。你有一个长度为 n 的排序序列，你将未排序的元素插入其中 - 你会得到 n+1 个元素长的排序序列。
区别如下:而插入排序仅适用于一个序列(最初是数组的第一个元素)并扩展它(使用下一个元素)。 但是，shell 排序具有递减增量，这意味着比较的元素之间存在间隙(最初为 n/2)。因此，有 n/2 个序列需要使用插入排序进行排序。在每一步中，增量都会缩小(通常仅除以 2.2)，序列数也会减少。最后一步没有间隙，算法退化为简单插入排序。
由于增量递减，大元素和小元素被快速移动以校正数组的一部分，并且比最后一步使用插入排序排序的速度非常快。这导致时间复杂度降低 O(n^(4/3))
关于algorithm - 壳排序和插入排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14619504/