C++最佳方法来排序链接列表？

Question

我有一个带有纹理索引的链接列表。他们是未分类的。我需要它们对它们进行排序，以便纹理索引按顺序升序排列。我总是可以声明另一个列表并阅读，但我很好奇如何排序。任何人都有我应该从哪里开始的建议或链接/我应该开始寻找这样做的建议或链接？另外我不使用STL列表。

谢谢！

Answer 1

由于缺乏随机访问，对链接列表进行排序并不那么高效。如果你知道你的列表不会很长，或者如果你能承受一点额外的复杂性，插入排序会更好，你总是可以使用一个简单的算法，如冒泡排序。

另一种可能比尝试对链表进行排序更好的方法是，将每个新节点插入正确的位置，以便在添加元素后对列表进行排序。

Answer 2

由于您没有随机元素访问权限，所以对mergesort（仍然为O(n log n)，即使对于列表）进行排序也可能最好。如果您可以切换到std::list，list::sort功能将为您处理。

或者使用非列表容器而不是列表，并且可以使用任何排序方法。