大佬教程收集整理的这篇文章主要介绍了使用迭代器的 C++ 合并排序，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
目前，我正在尝试创建一个简单的 C++ 合并排序程序。
using namespace std;
using Iterator = std::vector<int>::iterator;
using CIterator = std::vector<int>::const_iterator;
std::vector<int> merge(CIterator lefT_Begin,CIterator left_end,CIterator righT_Begin,CIterator right_end) {
std::vector<int> result;
CIterator left = lefT_Begin;
CIterator right = righT_Begin;
while (left != left_end && right != right_end) {
if (*left <= *right) {
result.push_BACk(*left);
left++;
} else {
result.push_BACk(*right);
right++;
}
}
while (left != left_end) {
result.push_BACk(*left);
left++;
}
while (right != right_end) {
result.push_BACk(*right);
right++;
}
return result;
}
我创建了一个合并函数，它基本上将两个已排序的向量连接为一个并返回它（我必须使用函数合并的以下返回类型）。然后尝试编写驱动程序函数合并排序我有以下代码，我认为它可以正常工作
voID merge_sort(Iterator begin,Iterator end) {
auto difference = distance(begin,end);
if (difference <= 1) {
return;
}
Iterator mIDdle = begin;
advance(mIDdle,difference / 2);
merge_sort(begin,mIDdlE);
merge_sort(mIDdle,end);
vector<int> result = merge(begin,mIDdle,end);
// But what to put here?
}
在注释标记的地方，我不明白要写什么才能将排序的数组在递归中向上移动一步。我试过了
begin = result.begin();
end = result.end();
但这显然不起作用
问题在于 @H_418_5@merge_sort 的类型签名假定采用就地算法：
void merge_sort(Iterator begin,Iterator end);
但是您的 @H_418_5@merge 过程不是就地的，而是返回数组的合并副本。您要么需要将 @H_418_5@merge 更改为就地，要么需要将 @H_418_5@merge_sort 更改为返回已排序的数组。后一种解决方案（更简单但效率较低）如下所示：
std::vector<int> merge_sort(Iterator begin,Iterator end) {
auto difference = distance(begin,end);
if (difference <= 1) {
return;
}
Iterator middle = begin;
advance(middle,difference / 2);
std::vector<int> left = merge_sort(begin,middlE);
std::vector<int> right = merge_sort(middle,end);
return merge(left.begin(),left.end(),right.begin(),right.end());
}
一种优化的自顶向下合并排序，它一次性分配第二个向量，然后使用一对相互递归的函数（...AtoA、...AtoB）根据递归级别交替合并方向. （我省略了原型）。
void MergeSort( typename std::vector<int>::iterator &ab,typename std::vector<int>::iterator &aE)
{
size_t sz = ae - ab;
if (sz < 2)
return;
std::vector<int> vb(sz); // temp vector
std::vector<int>::iterator bb = vb.begin();
std::vector<int>::iterator be = vb.end();
MergeSortAtoA(ab,ae,bb,bE);
}
void MergeSortAtoA( typename std::vector<int>::iterator &ab,typename std::vector<int>::iterator &ae,typename std::vector<int>::iterator &bb,typename std::vector<int>::iterator &bE)
{
size_t sz = ae - ab;
if(sz < 2) // if 1 element return
return;
std::vector<int>::iterator am = ab+(sz/2);
std::vector<int>::iterator bm = bb+(sz/2);
MergeSortAtoB(ab,am,bm);
MergeSortAtoB(am,bm,bE);
Merge(bb,be,ab);
}
void MergeSortAtoB( typename std::vector<int>::iterator &ab,typename std::vector<int>::iterator &bE)
{
size_t sz = ae - ab;
if(sz < 2){ // if 1 element,copy it
*bb = *ab;
return;
}
std::vector<int>::iterator am = ab+(sz/2);
std::vector<int>::iterator bm = bb+(sz/2);
MergeSortAtoA(ab,bm);
MergeSortAtoA(am,bE);
Merge(ab,bb);
}
void Merge( typename std::vector<int>::iterator &ab,typename std::vector<int>::iterator &am,typename std::vector<int>::iterator &bb)
{
std::vector<int>::iterator mb = ab; // left run iterator
std::vector<int>::iterator mm = am; // right run iterator
std::vector<int>::iterator bi = bb; // merge run iterator
while(1){ // merge data
if(*mb <= *mm){ // if mb <= mm
*bi++ = *mb++; // copy mb
if(mb < am) // if not end left run
conTinue; // conTinue (BACk to whilE)
while(mm < aE) // else copy rest of right run
*bi++ = *mm++;
break; // and return
} else { // else mb > mm
*bi++ = *mm++; // copy mm
if(mm < aE) // if not end of right run
conTinue; // conTinue (BACk to whilE)
while(mb < am) // else copy rest of left run
*bi++ = *mb++;
break; // and return
}
}
}
以上是大佬教程为你收集整理的使用迭代器的 C++ 合并排序全部内容，希望文章能够帮你解决使用迭代器的 C++ 合并排序所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。