在C++中,列表数据结构具有合并功能,该功能基本上删除源列表中的所有对象并将其放入目标列表中。
// source list will be empty after this operation
destinationList.merge(sourceList);
根据教程/示例,列表必须在合并操作之前进行排序。
destinationList.sort();
sourceList.sort();
destinationList.merge(sourceList);
我很困惑,因为如果需要对列表进行排序,为什么C++不通过在merge函数中调用sort函数来强制执行列表?
另一件事,我可以先合并未排序的列表,然后再对合并的列表进行排序,不是吗?
destinationList.merge(sourceList);
destinationList.sort();
最佳答案
merge
的目的是合并两个排序列表以创建一个新的排序列表,而无需执行其他排序。合并可以在线性时间内完成,而排序是O(n*log(n))
。
因为,如果列表已经排序,那将是非常低效的。
不可以。合并算法要求对输入进行排序,并根据它们生成排序列表。它通过比较输入列表的第一个元素,取下一个元素并将其附加到输出列表来工作。
您可以通过添加两个列表然后对结果进行排序来实现相同的目的;但是如果列表已经排序,那将是低效率的。