排序时列表类型是否影响算法选择？ArrayList和linked lists适配有差异吗？

答案是肯定的，列表的底层存储结构会直接决定排序算法的选型，确实存在两类列表适配的排序算法完全相反的情况，核心差异来自两种结构的操作效率特性：ArrayList属于连续内存存储的动态数组，支持O(1)时间的随机访问，但中间位置的插入、删除需要移动大量元素，时间复杂度为O(n)；而链表是离散节点通过指针关联的结构，不支持随机访问，跳转指定下标需要O(n)遍历，但节点的插入、删除只需要修改相邻节点的指针，时间复杂度为O(1)。

更适配ArrayList的排序算法 #

这类算法普遍依赖随机访问能力，换到链表上实现效率会下降至少一个数量级：

• 快速排序：需要频繁根据下标定位基准值两侧的元素做交换，在连续内存的数组上可以发挥最高效率，是绝大多数语言标准库对动态数组排序的默认选择
• 堆排序：核心的堆化操作依赖随机访问快速定位父节点、子节点的下标，在数组上实现成本极低，链表结构下根本无法高效完成节点定位
• 希尔排序：核心逻辑是按不同步长对分组元素做插入排序，需要频繁按步长跳转访问元素，用链表实现的话每次跳转都要遍历节点，效率会暴跌

更适配链表的排序算法 #

这类算法不需要随机访问，反而可以利用链表低插入删除成本的特性获得比在数组上更好的表现：

• 归并排序：在链表上可以实现比数组更高的效率，链表的节点合并只需要修改指针指向，不需要像数组排序一样额外开辟临时空间复制元素，也完全不需要随机访问，只要按顺序遍历节点即可，是链表排序的最优选择
• 插入排序：如果待排序链表本身有序度较高，插入排序只需要遍历找到插入位置后修改前后节点的指针即可，不需要像数组排序一样移动插入位置之后的所有元素，表现比在数组上更优秀

实际工业界的标准库都会做对应的适配，比如Java的Collections.sort()方法，底层就会先判断传入的列表是否为RandomAccess接口的实现类（比如ArrayList），如果是就调用适配数组的快速排序变体，否则就调用归并排序适配LinkedList这类链表结构。

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