1

您好我正在尝试对传递给函数的向量实现合并排序。这是我的代码，它不会对列表进行排序，但我不确定出了什么问题。当我输出原始向量和排序后的向量时，两者之间存在一些差异，但仍然没有排序。

void BestFit::findBest(){
    vector<double> distances;
    vector<double> sorted;
    distances = getDistance(0);
    printDistance(distances);
    sorted = sortDistance(distances);
    printDistance(sorted);
}

vector<double> BestFit::sortDistance(vector<double> distances){
    int mid = distances.size()/2;
    vector<double> left;
    vector<double> right;

    if(distances.size() > 1){
        for(int i = 0; i < mid; i++){
            left.push_back(distances[i]);
        }

        for(int i = mid; i < distances.size(); i++){
            right.push_back(distances[i]);
        }
        return sortDistanceHelp(left, right);
    }else{
        return distances;
    }
}

vector<double> BestFit::sortDistanceHelp(vector<double> left, vector<double> right){
    vector<double> result;
    if(left.size() > 1){
        left = sortDistance(left);
    }else if(right.size() > 1){
        right = sortDistance(right);
    }

    int count = 0;
    int left_count = 0;
    int right_count = 0;
    while(count < (left.size() + right.size())){
        if(left_count < left.size() && right_count < right.size()){
            if(left[left_count] <= right[right_count]){
                result.push_back(left[left_count]);
                left_count++;
            }else{
                result.push_back(right[right_count]);
                right_count++;
            }
        }else if(left_count < left.size()){
            result.push_back(left[left_count]);
            left_count++;
        }else{
            result.push_back(right[right_count]);
            right_count++;
        }
        count++;
    }

    return result;
}

这是未排序和排序的距离向量的输出。

未分类：

距离：0.679371 距离：1.263918 距离：1.575268 距离：0.117904 距离：3.851347 距离：2.317885 距离：0.899686 距离：3.916363 距离：1.513004 距离：0.446430

排序：

距离：0.679371 距离：1.263918 距离：1.575268 距离：0.117904 距离：2.317885 距离：0.899686 距离：3.851347 距离：3.916363 距离：1.513004 距离：0.446430

4

1 回答 1

0

我很确定这是问题所在。在sortDistanceHelp()：

if(left.size() > 1){
    left = sortDistance(left);
}else if(right.size() > 1){ //<<<===== ELSE SHOULD NOT BE HERE
    right = sortDistance(right);
}

它应该是这样的：

if(left.size() > 1)
    left = sortDistance(left);

if(right.size() > 1)
    right = sortDistance(right);

剩下的只是一个简单的合并算法，您可以将其用于您自己的目的，利用迭代器。这是我能想到的最简单的合并算法。它依赖于您的数据类型来支持operator <()，以及operator =()

template<typename ForwardIterator, typename OutputIterator>
void mergelists
(
    ForwardIterator first1,     // starting iterator of first sequence
    ForwardIterator last1,      // ending iterator of first sequence
    ForwardIterator first2,     // starting iterator of second sequence
    ForwardIterator last2,      // ending iterator of second sequence
    OutputIterator out1)        // output iterator for results
{
    while (first1 != last1 && first2 != last2)
    {
        // note the opposing less-comparison. equtes to (i1 <= i2)
        while (first1 != last1 && !(*first2 < *first1))
            *out1++ = *first1++;

        if (first1 != last1)
        {
            while (first2 != last2 && *first2 < *first1)
                *out1++ = *first2++;
        }
    }

    // doesn't really matter which one finished first
    //  only one of these will put one or more final
    //  nodes into the sequence.
    while (first1 != last1)
        *out1++ = *first1++;
    while (first2 != last2)
        *out1++ = *first2++;
}

再加上采用起始迭代器和大小的通用归并排序算法，我们有：

// general mergesort algorithm
template <typename Iterator>
void mergesort(Iterator first, size_t d)
{
    typedef typename std::iterator_traits<Iterator>::value_type value_type;

    Iterator last = first + d;
    size_t n = d/2;
    if (n == 0)
        return;

    if (n > 1) // no single elements
        mergesort(first, n);
    if (d > 1) // no single elements
        mergesort(first+n, d-n);

    // merge back into local sequence
    std::vector<value_type> vals;
    vals.reserve(d);
    mergelists(first, first+n, first+n, last, back_inserter(vals));

    // and copy into where it all began
    std::copy(vals.begin(), vals.end(), first);
}

下面是一个带有随机填充向量的示例用法：

int main()
{
    srand((unsigned)time(0));
    vector<int> data;

    // fill a vector with random junk.
    generate_n(back_inserter(data), 20, []() { return std::rand() % 99+1;});
    copy(data.begin(), data.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    mergesort(data.begin(), data.size());
    copy(data.begin(), data.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
    return 0;
}

样品运行 I

54 75 14 59 69 18 65 40 52 77 65 43 87 80 99 44 81 40 70 37 
14 18 37 40 40 43 44 52 54 59 65 65 69 70 75 77 80 81 87 99

样品运行 II

53 91 27 29 47 31 20 90 12 18 16 75 61 94 60 55 66 44 35 26 
12 16 18 20 26 27 29 31 35 44 47 53 55 60 61 66 75 90 91 94
于 2013-03-09T06:27:04.880 回答