通过值传递的C++合并排序

Question

我想递归实现合并排序算法，只通过向函数传递矢量值（无左或右索引）。以下代码中的while循环在将要排序的列表作为指针void merge_sort_array(int* v, int l, int r)或引用void merge_sort_ref(vector<int>& v, int l, int r)进行传递时起作用，但我无法理解为什么下面的代码不能正确地对我的列表进行排序。我有一种感觉，这与i, j, k的起始值或我的while循环中的界限有关，但我已经尝试了任何对我有意义并且无法理解的东西。

#include <iostream> 
#include <ctime> 
#include <cstdlib> 
#include <vector> 
#include <algorithm> 

using namespace std; 
vector<int> merge_sort_value(vector<int> v) { 
    int n = v.size(); 
    if(n == 1){ 
     return v; 
    } 
    else{ 
     int m = n/2; 
     vector<int> v1(v.begin(), v.begin()+m); 
     vector<int> v2(v.begin()+m, v.begin()+n); 
     merge_sort_value(v1); 
     merge_sort_value(v2); 
     vector<int> tmp(v.begin(), v.begin()+m); 
     int i = 0; 
     int j = m; 
     int k = 0; 
     while((i < m) or (j < n)){ 
      if(i == m){ 
       v[k] = v[j]; 
       j +=1; 
      } 
      else if((j == n) or (tmp[i] < v[j])){ 
       v[k] = tmp[i]; 
       i+=1; 
      } 
      else{ 
       v[k] = v[j]; 
       j+=1; 
      } 
      k+=1; 
      # print output for debugging 
      for(auto x = v.begin(); x != v.end(); ++x) 
       cout << *x << " "; 
      cout << "" << endl; 
      cout << i << "\t"<< j << "\t" << k << endl; 
     } 
     return v; 
    } 
} 

int main(int argc, char** argv) { 
    vector<int> v(10); 

    for(int i=0; i < 10; ++i) 
     v[i] = rand() % 100; 

    v = merge_sort_value(v); 
    return 0; 
} 

我已经包含了参考下面的样本输出：

28 28 
0 2 1 
28 80 
1 2 2 
21 21 
0 2 1 
21 92 
1 2 2 
14 92 21 
1 1 1 
14 92 21 
1 2 2 
14 92 21 
1 3 3 
14 28 14 92 21 
0 3 1 
14 80 14 92 21 
1 3 2 
14 80 28 92 21 
2 3 3 
14 80 28 92 21 
2 4 4 
14 80 28 92 21 
2 5 5 
21 57 
1 1 1 
21 57 
1 2 2 
78 83 
1 1 1 
78 83 
1 2 2 
78 78 83 
0 2 1 
78 83 83 
0 3 2 
78 83 96 
1 3 3 
21 57 96 78 83 
1 2 1 
21 57 96 78 83 
2 2 2 
21 57 96 78 83 
2 3 3 
21 57 96 78 83 
2 4 4 
21 57 96 78 83 
2 5 5 
21 28 14 92 21 21 57 96 78 83 
0 6 1 
21 57 14 92 21 21 57 96 78 83 
0 7 2 
21 57 80 92 21 21 57 96 78 83 
1 7 3 
21 57 80 28 21 21 57 96 78 83 
2 7 4 
21 57 80 28 14 21 57 96 78 83 
3 7 5 
21 57 80 28 14 92 57 96 78 83 
4 7 6 
21 57 80 28 14 92 21 96 78 83 
5 7 7 
21 57 80 28 14 92 21 96 78 83 
5 8 8 
21 57 80 28 14 92 21 96 78 83 
5 9 9 
21 57 80 28 14 92 21 96 78 83 
5 10 10 

谢谢，任何帮助是非常感谢！

Answer 1

审查你的代码之后好像你正在做的算法，它自身并用C++的错误作为的语言，所以我已经编辑你的算法更整洁，更可读的算法，我将解释代码的某些部分

代码

#include <iostream> 
#include <ctime> 
#include <cstdlib> 
#include <vector> 
#include <algorithm> 

using namespace std; 
vector<int> merge_sort_value(vector<int> v) { 
    int n = v.size(); 
    if(n == 1){ 
    return v; 
    } 
    else{ 
    int m = n/2; 
    vector<int> v1(v.begin(), v.begin()+m); 
    vector<int> v2(v.begin()+m, v.begin()+n); 
    v1 = merge_sort_value(v1); /* passing by value will left v1 with no sorting so you need to copy from the returned 
    object */ 
    v2 = merge_sort_value(v2); 
    int i = 0; 
    int j = 0; 
    int k = 0; 
    const size_t left_vecS = v1.size(); 
    const size_t right_vecS = v2.size(); 

    while (i<left_vecS&&j<right_vecS) { // we must keep i (AND) j valid 
     if (v1[i] < v2[j]) 
     v[k++] = v1[i++]; 

     else 
     v[k++] = v2[j++]; 
    } 

     while(i<left_vecS) // if we sorted v2 then what insert the rest of v1 in v as what kept from v1 will be sorted 
     v[k++] = v1[i++]; 


     while(j<right_vecS) 
     v[k++] = v2[j++]; 
    } 
    return v; 
    } 


int main(int argc, char** argv) { 
    vector<int> v(10); 
    std::vector<int> x; 

    for(int i=0; i < 10; ++i) 
    v[i] = rand() % 100; 

    v = merge_sort_value(v); 

    for(auto&i:v) 
    std::cout << i << std::endl; 

    return 0; 
} 

我摆脱了排序函数内部印刷的，所以我们保持代码的清洁

2 - 您在语言级别做的第一个错误是您没有将从merge_sort_value返回的已排序矢量对象复制到矢量中（我在注释中的代码中提到过），所以这是第一个事情要记住

3-算法的逻辑部分是我不太清楚，因为我没怎么看你整理特别是部分else if ((j == n) or (tmp[i] < v[j])) { v[k] = tmp[i]; i += 1; }

像你比较无序子矢量到另一个未排序的矢量，你又给它未排序的值（你必须比较V1对V2） 整个逻辑是错过了我认为你需要审查它

无论如何，我希望帮助