sorting - 使用双向链表的插入排序的复杂性？

Question

插入排序需要通过在通过数组实现时移动已排序列表的元素来按排序顺序插入元素。如果我们不使用数组，而是使用双向链表，那么时间复杂度是多少？

时间复杂度是 O(n^2)？为什么？如果我们考虑插入 n 个元素，那么它将是 log(1) + log(2) + log(3) + ..... + log(n) - n 次 n 个元素，因此复杂度应该是 O(nlogn)

Answer 1

插入链表需要时间 O( n )，而不是 O(lgn )，因为您必须导航链接结构才能找到插入点。