大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
本文senlie原版的，转载请保留此地址：http://blog.csdn.net/zhengsenlie
merge (应用于有序区间)
————————————————————————–
描写叙述：将两个经过排序的集合S1和S2。合并起来置于还有一段空间。所得结果也是一个有序(sorted)序列
思路：
1.遍历两个序列直到当中一个结束了
2.假设序列一的元素较小。将它放到结果序列中，并前进 1
3.假设序列二的元素较小，将它放到结果序列中。前前进 1
4.遍历结束后。将还没有遍历完的序列拷贝到结果序列的尾部
复杂度：O(m+n)
源代码：
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result) {
while (first1 != last1 && first2 != last2) {
if (*first2 < *first1) {
*result = *first2;
++first2;
}
else {
*result = *first1;
++first1;
}
++result;
}
return copy(first2, last2, copy(first1, last1, result)); // 之前一直不懂为什么 copy 之类的算法要返回一个指向 操作完后的序列的 last 的迭代器。这行代码非常好地解释了原因}
演示样例：
int main()
{
int A1[] = { 1, 3, 5, 7 };
int A2[] = { 2, 4, 6, 8 };
const int N1 = sizeof(A1) / sizeof(int);
const int N2 = sizeof(A2) / sizeof(int);
merge(A1, A1 + N1, A2, A2 + N2,
ostream_iterator<int>(cout, " "));
// The output is "1 2 3 4 5 6 7 8"
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116746.html原文链接：https://javaforall.net
