插入排序算法的改进

Question

如果使用双向链表代替数组，是否有可能提高插入排序算法的运行时间？

非常感谢。

Answer 1

不，从某种意义上说不是。插入排序有几种变体，所以让我们讨论一下列表左侧按升序排序而右侧不排序的那种。在每次迭代中，我们找到未排序列表中的第一个(最左边的)元素，调用< code>x，然后通过排序列表向后迭代，查看该元素属于哪里。如果列表是一个数组，我们取出新元素，并在排序后的列表中向右移动条目，直到我们找到条目所属的位置，并把它放在那里。因此，我们遍历列表中的< code>n项，对于其中的每一项，我们遍历排序列表中的项，第一次迭代时为0项，下一次迭代时为1项，之后为2项，...高达< code>n因此，平均来说，对于O(n^2).的总运行时间，我们的< code>n次迭代中的每一次迭代，我们进行了高达< code>n/2次比较/交换

如果您将其设置为双链列表，则唯一会发生变化的是，在迭代排序列表时，不要向右移动一个项目，而是将它们保留在原处，然后将新项目放到适当的位置以修复列表。但它仍然是n / 2平均比较和指针反引用（以查找列表中的下一个节点），因此big-O运行时是相同的。实际上，在现实生活中可能会更慢，因为指针取消引用可能不适合缓存，并且比在数组中右向右移动项目需要更多的时间。