java排序单链表与排序双链表
如果之前有人回答过，请给我指出正确的方向
所以，我已经四处闲逛了一段时间，读了一些关于分类的书。然而，我想知道，为单链表和双链表（以及与数组结构相比的链表结构）选择一个好的排序算法的主要区别是什么
我知道（假设我们使用的是OO语言），类型与要排序的元素等有关（基本类型通常比复杂对象更快）。我在比较Java字符串和整数
据我所知，在处理链接结构时，我们可能应该排除快速排序和插入排序，因为它们涉及很多索引
这个问题可能不好，但正如我提到的，请给我指出另一个来源，在那里我可以阅读关于选择正确算法的信息（而不是如何实现算法）
# 1 楼答案
我想说没有区别。对于一般的基于比较的排序算法，您受到O（n）读取和O（log（n））比较的限制
以合并排序为例，切碎列表，直到到达基本情况（一个包含一个项目的列表已经排序）。然后，你要合并和交换那些不符合顺序的项目。在单链表或双链表中交换都是O（1）操作
也许对于双链表，如果你知道你的数据将遵循某种“部分排序”结构的顺序，比如向前或向后“排序更高”，那么你可以写你的列表，沿着特定的方向走，从而产生更少的交换，但最终你仍然有一个O（n logn）算法，具有非常，由于只进行O（logn）比较，交换更少，所以运行时速度略微加快