据我所知,inplace_merge与sort完全相同,只是它仅在某些情况下才有效(当容器已经位于两个已排序的部分中时)。
换句话说,这两者之间有区别:
int first[] = {1,3,5,7};
int second[] = {2,4,6,8};
vector<int> v(8);
vector<int>::iterator it;
copy(first,first+4, v.begin());
copy(second,second+4, v.begin()+4);
inplace_merge(v.begin(), v.begin()+4, v.end())
。
int first[] = {1,3,5,7};
int second[] = {2,4,6,8};
vector<int> v(8);
vector<int>::iterator it;
copy(first,first+4, v.begin());
copy(second,second+4, v.begin()+4);
sort(v.begin(), v.end())
唯一的区别是效率吗?
最佳答案
它们的复杂性是不同的:
O(N²)
,具体取决于您的STL实现使用的排序算法。 O(N*log(N))
情况最糟,而O(N-1)
的情况最糟,因此它(永远不会比sort()
慢)(输入相同)。 另外,正如其他人指出的那样,
inplace_merge()
是stable:它保留排序键相同的项目的顺序。 sort()
不保证这一点。 stable_sort()可以,最坏情况下的复杂度是O(N*log(N)²)
。