如果之前已经回答过这个问题，请指出正确的方向!
所以，在阅读有关排序的内容时，我已经闲逛了一段时间。然而，我想知道，为单链表与双链表(以及与数组结构相比的链接结构)选择良好的排序算法之间的主要区别是什么？
我知道(假设我们使用面向对象语言)类型对要排序的元素等很重要(原始类型通常比复杂对象更快)。我正在比较 Java 字符串和整数。
据我了解，在处理链接结构时，我们可能应该排除快速排序和插入排序，因为它们大量处理索引。
这个问题可能很糟糕，但正如我所提到的，请向我指出另一个来源，我可以在其中阅读有关选择正确算法的信息(而不是如何实现算法)。
最佳答案
是的，尝试远离链接结构中的索引的想法是一个很好的指导方针。但请注意，这不是严格的规则。
I know that (assuming we're in an OO-language) the type matters on the elements to be sorted etc (primitive types are typically faster than complex objects). I was comparing Java Strings and integers.
这个想法非常好!基本类型具有快速比较时间，因此对于快速排序来说这些效果很好(假设它们不在链接结构中)。
如果字符串很长，比较字符串的成本可能会非常高。因此，对大量字符串进行合并排序是一个好主意。所以这里的主要思想是，如果我们进行昂贵的比较，则首选合并排序。如果我们进行快速比较，快速排序可能是首选(假设我们有很好的技术来选择 Pivot value )。
对于链接结构，一个想法也可以是将所有列表复制到堆中，然后从那里执行 Heap Sort 。但如果我们的内存有限，这并不是解决问题的好方法。
如果您无法决定适用于您的代码的良好排序算法，请遵循语言标准。例如，请参阅此主题:Why Collections.sort uses merge sort instead of quicksort? [closed] .
一个小列表:
- 如果您无法使用更多内存:快速排序。
- 如果您无法承受缓慢的比较:合并排序。
- 如果您有一个非常(非常)大的结构:快速排序或合并排序。
- 如果有链接结构:合并排序。
当然，有很多场景组合，人们必须仔细选择。还有更多的排序算法可供使用。我只提到了 Merge 和 Quick，因为你似乎对它们很了解。
关于java - 单链表排序与双链表排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48813137/