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

唯一的区别是效率吗?

最佳答案

它们的复杂性是不同的:

  • sort()最糟糕的情况是O(N²),具体取决于您的STL实现使用的排序算法。
  • inplace_merge()O(N*log(N))情况最糟,而O(N-1)的情况最糟,因此它(永远不会比sort()慢)(输入相同)。

  • 另外,正如其他人指出的那样,inplace_merge()stable:它保留排序键相同的项目的顺序。 sort()不保证这一点。 stable_sort()可以,最坏情况下的复杂度是O(N*log(N)²)

    07-24 09:46
    查看更多