实现合并排序C++

Question

嗨我想实现一个合并排序的向量，我传入函数。这里是我的代码，它不排序列表，但我不知道什么是错的。当我输出原始矢量和已排序的矢量时，两者之间存在一些差异，但它仍未排序。

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.6793 71 距离：1.263918 距离：1.575268 距离：0.117904 距离：2.317885 距离：0.899686 距离：3.851347 距离：3.916363 距离：1.513004 距离：0.446430

Answer 1

我敢肯定，这就是问题所在。在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++; 
} 

再加上一般的归并排序算法以起始iterator和大小，我们有：

// 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; 
} 

样品试验我

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