C++ STL :: inplace_merge和sort之间的区别是什么

Question

据我所知,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())

唯一的区别是效率吗？

Answer 1

它们的复杂性不一样:

• sort()的情况最糟糕O(N²),取决于STL实现使用的排序算法.

• inplace_merge()具有最坏情况O(N*log(N))和最佳情况O(N-1),因此它永远不会慢于sort()(使用相同的输入).

此外,正如其他人所指出的那样,它inplace_merge()是稳定的:它保留了排序键相同的项目的顺序.sort()不保证这一点.stable_sort()确实如此,其最坏情况的复杂性是O(N*log(N)²).

Answer 2

两个区别:

• 稳定性: inplace_merge是稳定的算法(它会保持相同的项目以相同的顺序都内的子范围和你们两个原来的范围之间).
  因此,当您处理非基本类型的容器时,或者排序函数被解除时,结果可能会略有不同.当然,对于integers的容器,你不会注意到任何差异:)
• 效率:正如您所说,鉴于您已经有两个已排序的子集,inplace_merge必须以不同的方式实现,因此可能更有效.这个函数存在的唯一事实告诉了很多.