在C++中,为什么要求在合并之前必须对列表进行排序

Question

在C++中,列表数据结构具有合并功能,该功能基本上删除源列表中的所有对象并放入目标列表.

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

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

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

我很困惑,因为如果需要排序列表,为什么C++不会通过在合并函数中调用sort函数来强制执行它？

另外一件事,我可以先合并未排序的列表,然后我可以对合并列表进行排序,是不是也一样？

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

Answer 1

为什么要求在合并之前必须对列表进行排序？

目的merge是合并两个排序列表以创建新的排序列表,而无需执行另一种排序的开销.合并可以在线性时间内完成,而排序则是O(n*log(n)).

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

因为,如果列表已经排序,那将是非常低效的.

另外一件事,我可以先合并未排序的列表,然后我可以对合并列表进行排序,是不是也一样？

否.合并算法要求对输入进行排序,并从中生成排序列表.它的工作原理是比较输入列表的第一个元素,取较低的值,然后将其附加到输出列表中.

您可以通过附加两个列表然后对结果进行排序来实现相同的目的; 但如果列表已经排序,那将再次效率低下.