插入排序算法改进探究：使用双向链表替代数组能否提升运行效率

绝大多数场景下无法有效改善运行时间，甚至会比数组实现的插入排序慢数倍到数十倍，仅在非常特殊的场景下会有性能收益，具体原因如下：

• 数组实现插入排序的核心开销来自两部分：查找插入位置的O(k)开销（k为已排序序列长度）、插入点后元素平移的O(k)开销。双向链表确实可以把第二部分开销降到O(1)——只需要修改插入位置前后两个节点的指针，不需要移动任何实际元素。
• 但双向链表会带来两个更致命的性能损耗：
  1. 不支持随机访问，原本数组实现可以用二分查找把查找插入位置的开销降到O(logk)，双向链表只能从头遍历已排序序列，查找开销固定为O(k)，整体时间复杂度仍然是O(n²)，没有量级上的优化。
  2. 内存不连续导致缓存命中率极低。数组是连续存储的内存块，CPU的缓存预取机制可以把后续待访问的元素提前加载到缓存，遍历效率极高；而双向链表的节点通常是离散分配在堆内存中，每次访问节点都大概率触发缓存失效，访存开销是数组的几十倍，完全抵消了省去元素平移带来的收益。
• 仅有的适用场景是存储的单个元素体积极大（比如单元素大小超过1KB），此时数组平移元素的内存拷贝开销超过了链表缓存失效和遍历的额外开销，才有可能出现性能提升。

内容的提问来源于stack exchange，提问作者user16438868