實現合併排序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