使用向量对C++进行MergeSort

Question

我已经尝试修复我的代码一段时间了，虽然它确实打印出了数字，但它只是按照我输入的顺序打印出来。它并没有按照预期进行合并排序，不知道我是否遗漏了键入的内容，但我非常感谢您的反馈和帮助。还有它说static void ordena(typename std::vector<T>::iterator &&b, typename std::vector<T>::iterator &&e)的部分，因为它需要我把它交上来，所以不能更改。

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
template<typename T>
class mergeSort {
public:
static void ordena(typename std::vector<T>::iterator &&b, typename std::vector<T>::iterator &&e) {
if (b-e+1 <= 1)
return;
auto iter = b + (b-e+1) / 2;
vector<T> v1(b, iter);
vector<T> v2(iter, e);
ordena(v1.begin(),v1.end());
ordena(v2.begin(),v2.end());
vector<T> v3;
merge(v3, v1, v2);
}
static void merge(vector<T> &v3, vector<T> &v1, vector<T> &v2){
auto siz1 = v1.size();
auto siz2 = v2.size();
size_t p1 = 0;
size_t p2 = 0;
while (p1 < siz1 && p2 < siz2) {
if (v1.at(p1) < v2.at(p2))
v3.push_back(v1.at(p1++));
else
v3.push_back(v2.at(p2++));
}
while (p1 < siz1) v3.push_back(v1.at(p1++));
while (p2 < siz2) v3.push_back(v2.at(p2++));
}
};
template<typename T>
std::string to_string(const std::vector<T> &elements){
std::string str{};
for(T e : elements) str += std::to_string(e) + ", ";
return str.substr(0,str.length()-2);
}
int main()
{
vector<int> elements;
elements.push_back(100);
elements.push_back(10);
elements.push_back(80);
elements.push_back(30);
elements.push_back(60);
elements.push_back(50);
elements.push_back(40);
elements.push_back(70);
elements.push_back(20);
elements.push_back(90);
mergeSort<int>::ordena(elements.begin(), elements.end());
std::cout << "First ordered sequence : " << to_string(elements) << std::endl;
}

Answer 1

合并(v3，v1，v2(后，将v3复制到*b到*(e-1(。这不是一种有效的方法，但它应该起作用。

// only single reference is needed
static void ordena(typename std::vector<T>::iterator &b, typename std::vector<T>::iterator &e) {
// ...
merge(v3, v1, v2);
std::copy(v3.begin(), v3.end(), b);

---

您也可以更改merge，将迭代器作为第一个参数

merge(b, v1, v2);