在C++中，为什么需要在合并前对列表进行排序

Question

在C++中，列表数据结构有一个合并函数，它基本上删除源列表中的所有对象并放入目标列表中。

// source list will be empty after this operation
destinationList.merge(sourceList);

根据教程/示例，必须在合并操作之前对列表进行排序。

destinationList.sort();
sourceList.sort();
destinationList.merge(sourceList);

我感到困惑是因为如果需要排序列表，为什么C++不通过在合并函数中调用排序函数来强制执行排序？

另外，我可以先合并未排序的列表，然后对合并列表进行排序，这不是一样的吗？

destinationList.merge(sourceList);
destinationList.sort();

Answer 1

为什么需要在合并前对列表进行排序？

merge的目的是合并两个排序列表以创建一个新的排序列表，而不需要执行另一个排序。合并可以在线性时间内完成，而排序是O(n*log(n))。

为什么c++不通过调用合并函数中的排序函数来强制执行它？

因为，如果列表已经被排序，那将是可怕的低效。

另外，我可以先合并未排序的列表，然后对合并列表进行排序，这不是一样的吗？

不是的。合并算法要求对输入进行排序，并从输入中生成一个排序列表。它的工作方式是比较输入列表的第一个元素，取下一个元素，并将其附加到输出列表中。

您可以通过追加两个列表，然后对结果进行排序，从而实现相同的目标；但是，如果列表已经被排序，那么这将是效率低下的。

Answer 2

假设你在这里的意思是“合并”而不是“合并”，那就有点不同了。

在将列表组合在一起之前，不需要对它们进行排序。根据您的需求，有3种不同的组合列表的方法

合并排序列表：

list1.merge( list2 ) // Complexity linear. Assumes list1 & list2 are sorted

将列表中的所有元素移到另一个元素中：

list1.splice( std::end( list1 ), list2 ) //Complexity: constant

将列表中的某些元素复制到另一个列表中：

list1.insert( it1, it2 )// Complexity: linear, it1 & it2 are iterators pointing into list2

因此，实际上，C++标准为该特定任务提供了多个算法，每个算法都具有最佳的复杂度。