代码之家  ›  专栏  ›  技术社区  ›  UgaBugha

用向量合并C++

  •  0
  • UgaBugha  · 技术社区  · 2 年前

    我已经尝试修复代码一段时间了,虽然它确实打印出了数字,但它只按照我给出的顺序打印出来。它并没有像预期的那样进行合并排序,不知道我是否漏掉了键入的内容,但非常感谢您的反馈和帮助。还有它说 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;
    }
    
    0 回复  |  直到 2 年前
        1
  •  0
  •   rcgldr    2 年前

    合并(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);