C++ STL:: inplace_merge 和 sort 有什么区别
据我所知， 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())
唯一的区别是效率吗？
As far as I can tell, inplace_merge does the exact same thing as sort, except it only works in certain circumstances (When the container is already in two sorted parts).
In other words, is there an difference between these two:
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())
Is the only difference going to be efficiency?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
它们的复杂度不一样：
sort() 有最坏的情况
O(N²)，具体取决于 STL 实现所使用的排序算法。inplace_merge() 最坏情况为
O(N *log(N))和O(N-1)的最佳情况，因此它永远不会比sort()慢（具有相同的输入）。此外，正如其他人指出的那样，
inplace_merge()是稳定 ：它保留排序键相同的项目的顺序。sort()不保证这一点。 stable_sort() 确实如此，其最坏情况复杂度为O( N*log(N)²)。Their complexity is not the same:
sort() has a worst case of
O(N²), depending on the sorting algorithm used by your STL implementation.inplace_merge() has a worst case of
O(N*log(N))and a best case ofO(N-1), so it will never be slower thansort()(with the same inputs).Also, as others have pointed out,
inplace_merge()is stable: it preserves the ordering of items whose sort key is the same.sort()does not guarantee this. stable_sort() does, and its worst-case complexity isO(N*log(N)²).两个区别：
inplace_merge是一种稳定的算法（它将在两个原始范围之间的子范围和内以相同的顺序保留相同的项目。因此，当您处理非基本类型的容器时，或者当您的排序函数被解救时，结果可能会略有不同。
当然，使用
integers 容器，您不会注意到任何差异:)inplace_merge必须以不同的方式实现，因此可能会更有效。这个函数的存在这一事实就说明了很多。Two differences:
inplace_mergeis a stable algorithm (it will keep equal items in the same order both within subranges and between you two original ranges).So, there might be a slight difference in the result when you deal with containers of non-primitive types, or when your sort function is extricated.
Of course, with container of
integers, you will not notice any difference :)inplace_mergemust be implemented in a different way and will therefore probably be more efficient. The single fact that this function exists tells much.sort方法按升序对范围内的 2 个已排序元素（first、last）进行排序。inplace_search将 2 个排序范围（first、middle）和（middle、last）合并为一个组合排序范围（first） em>，最后）。为了使
inplace_merge高效，2 个子范围必须进行排序（这就是区别）。此外，inplace_merge理论上不稳定，（但是在 C++ 中稳定），但它需要高效的内存才能完成（最后 - 第一个） - 1 次比较，否则它类似于排序（进行 O(n log n) 比较）。The
sortmethod sorts 2 sorted elements in the range (first, last) in ascending order.inplace_searchmerges the 2 sorted range (first, middle) and (middle, last) into a combined sorted range (first, last).For
inplace_mergeto be efficient, the 2 subranges must be sorted (that's the difference). Additionally,inplace_mergeis theoretically unstable, (but stable in C++) but it requires efficient memory to do (last - first) - 1 comparisons else it's similar to sort (which does O(n log n) comparisons).