Kor*_*icz 23
仅对其他范围排序,然后使用std :: merge.
- merge需要分开输入和输出,这里使用的正确算法是`inplace_merge`. (12认同)
- 虽然你的帖子不是仅链接答案的经典案例,因为它至少包含一个函数的名称,但它仍然只比threashold高一点.请提供至少一个简约的用法示例,最好与OPs问题相关联.我知道很多人都赞成这一点,但如果链接被删除,他们也会投票吗？ (3认同)
gal*_*p1n 20
void foo( std::vector<int> & tab, int n ) {
std::sort( begin(tab)+n, end(tab));
std::inplace_merge(begin(tab), begin(tab)+n, end(tab));
}
编辑2
auto it = std::adjacent_find(begin(tab), end(tab), std::greater<int>() );
if (it!=end(tab)) {
it++;
std::sort( it, end(tab));
std::inplace_merge(begin(tab), it, end(tab));
}
- 您可以使用[`std :: is_sorted_until`](http://en.cppreference.com/w/cpp/algorithm/is_sorted_until)代替`std :: adjacent_find` (10认同)
- 同样,标准的`inplace_merge`正式是一个"假的","模拟的"就地合并.该标准允许它在不合适的地方工作,并允许它执行完整的排序.坦率地说,我不记得曾经看到过一个诚实的实施,而不是一个完整的.该算法太复杂而无法理解.如果你知道一个,请告诉我. (2认同)
最佳解决方案是独立地对尾部进行排序,然后执行就地合并,如此处所述
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.5750
该算法非常复杂,通常被认为"不值得努力".
当然,使用C++,您可以随时使用std::inplace_merge.但是,该算法的名称极具误导性.首先,不能保证std::inplace_merge实际就地工作.当它实际就位时,并不能保证它不会被实现为完整的排序.在实践中,它归结为尝试它并看它是否足够好用于你的目的.
但是如果你真的想要就地制作并且正式比完全排序更有效,那么你将不得不手动实现它.STL可能有助于一些实用程序算法,但它没有提供"只需几次调用标准函数"类型的任何可靠解决方案.