3

这是关于使用 STL std::sort 函数进行排序背后的机制的一般问题。我读过一些关于排序的文章，一般来说，排序向量比排序链表更快。这对于结构/对象的向量和链表是否正确？对于结构的链表，我觉得只需修改索引即可轻松实现排序。另一方面，向量的排序似乎涉及物理地切换结构/对象数据的数据位置，因为它们是连续的（这是真的吗？）。在那种情况下，似乎对链表进行排序会更快。

编辑！！！：现在有图片：

在此处输入图像描述

所以我想这个问题更好用：对对象排​​序、对链表排序还是对向量排序更快（尽管这可能取决于对象的大小）？此外，链表的排序是否如 3) 所示完成，向量的排序是否如 2) 所示完成？

4

3 回答 3

3

排序list是专门的（即list具有排序功能，不能用 排序std::sort）。

void sort();
template <class Compare> void sort(Compare comp);

复杂性：大约 N log(N) 比较，其中 N == size()。

std::sort概括地说。

template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);

复杂性：O(N log(N))（其中 N == last - first）比较。

请注意，结果与std::list::sort相同std::stable_sort。注意标准中没有信息，sort应该如何实现。它是实现定义的。

于 2012-09-14T21:12:20.407 回答
2

您始终可以通过对索引或指针或其他任何并行集合进行排序来进行排序。这适用于列表和向量。

排序列表较慢的原因是最快的排序算法需要随机访问，即能够立即获取给定索引处的值的能力。你不会用列表来理解这一点。要获得链表中的第 10 项（例如），您必须从头开始并向前移动 10 次。

于 2012-09-14T21:16:48.933 回答
2

你是对的，std::vector如果复制一个元素很慢，那将会很慢。C++11 引入了可能有帮助的移动语义，元素可以移动而不是复制。

链表很容易使用归并排序进行排序，与任何其他好的排序算法一样，它是 O(n log n)。区别在于开销。

与往常一样，如果结果对您很重要，那么对您的特定案例进行基准测试是一个好主意。

于 2012-09-14T21:26:14.243 回答