试图将伪代码转换为MERGE SORT的实际代码

Question

我想为家庭作业实现合并排序，我们应该这样做，因此它与此伪代码非常相似（假定数组以1开头）。

/*MERGESORT(A, p, r)] 
    if p < r 
     q = (p+r)/2 
     MERGESORT(A,p,q) 
     MERGESORT(A,q + 1, r) 
     MERGE(A,p,q,r) 

MERGE(A,p,q,r) 
    n1 = q - p + 1 
    n2 = r - q 
    let L[1...n1 + 1] and R[1...n2 + 1] be new arrays 
    for i = 1 to n1 
     L[i] = A[p + i - 1] 
    for j = 1 to n2 
     R[j] = A[q + j] 
    L[n1 + 1] = INFINITY 
    R[n2 + 1] = INFINITY 
    i = 1 
    j = 1 
    for k = p to r 
     if L[i] <= R[j] 
      A[k] = L[i] 
      i = i + 1 
     else 
      A[k] = R[j] 
      j = j + 1*/ 

其中A是整个数组，p q和r是索引，A [p ... r]是需要排序的数据。 这是我迄今所做的：

void CensusData::mergeSort(int type) { 
     if(type == 0) //STOPPED FOR DEBUGGING 
      MERGE_SORT(type, 0, data.size() - 1); 
    } 

    void CensusData::MERGE_SORT(int type, int p, int r){ 
     //int q; 
     //cout << "data size " << data.size() << endl; 
     std::cout << "MERGE_SORT START ///("<< p << ", " << r << ")" <<std::endl; 
     if(p < r) 
     { 
      int q = (p + r)/2; 
      MERGE_SORT(type, p, q); 
      MERGE_SORT(type, q + 1, r); 
      MERGE(type, p, q ,r); 
     } 
    } 

    void CensusData::MERGE(int type, int p, int q, int r){ 
     if(type == 0) 
     { 
      std::cout << "MERGING WITH: (" << p << ", "<< q <<", " << r<< ")"<< std::endl; 
      //int n1; 
      //int n2; 
      int n1 = q - p + 1; 
      int n2 = r - q; 
      cout << "N1: " << n1 <<" N2:" << n2 << endl; 
      Record* L[n1 + 1]; 
      Record* R[n2 + 1]; 
      L[n1 + 1] = NULL; 
      R[n2 + 1] = NULL; 
      for(int i = 0; i < n1; i++) 
      { 
       if (L[i] == NULL) 
        continue; 
       cout << "P, I: " << p <<", "<< i<< endl; 
       cout << "filling array L: " << data[p + i]->population << endl; 
       L[i] = data[p + i]; 
       cout<< L[i]->population << endl; 
      } 
      //cout << "J: " << j << endl; 
      for(int j = 0; j < n2; j++) 
      { 
       if(R[j] == NULL) 
        continue; 
       cout << "filling array R: " << data[q + j + 1]->population<<endl; 
       R[j] = data[q + j + 1]; 
       cout << R[j]->population << endl; 
      } 

      int i = 0; 
      int j = 0; 
      for(int k = p; k <= r; k++) 
      { 
       if(L[i]->population < R[j]->population) 
       { 
        cout << "TRUE" << endl; 
        data[k] = L[i]; 
        i = i + 1; 
       } 
       else 
       { 
        cout << "FALSE" << endl; 
        data[k] = R[j]; 
        j = j + 1; 
       } 
      } 
       std::vector<Record*>::iterator it = data.begin(); 
    while (it != data.end()) { 
     std::cout << *(*it)->city << ", " 
       << *(*it)->state << ", " 
       << (*it)->population << std::endl; 
     } 
    } 

所有我可以告诉你的是，这是行不通的，它赛格故障所有的地方，我一直在这6小时，去一事无成，帮助将不胜感激。注意：记录是也称为数据的向量。这里也是输入和输出：

Vina, California, 237 
San Francisco, California, 812826 
Santa Fe, New Mexico, 68642 
Roseville, California, 1293 
New York, New York, 283822 
Potatoville, Brentland , 283822 

输出：

Vina, California, 237 
Santa Fe, New Mexico, 68642 

Program received signal SIGSEGV, Segmentation fault. 
0x00445dd7 in std::basic_ostream<char, std::char_traits<char> >& std::operator<< <char, std::char_traits<char>, std::allocator<char> >(std::basic_ostream<char, std::char_traits<char> >&, std::basic_string<char, std::char_traits<char>, std::allocator<char> > const&)() 
    at /usr/lib/gcc/i686-pc-cygwin/3.4.4/include/c++/iostream:77 
77  static ios_base::Init __ioinit; 

Answer 1

这里是一个问题，我看到：

Record* L[n1 + 1]; 
    Record* R[n2 + 1]; 
    L[n1 + 1] = NULL; 
    R[n2 + 1] = NULL; 

您可以定义X元素的数组，并在下一次尝试为x + 1元素设置一个值。 请记住，数组的索引从0到n-1。

Answer 2

除了功课外，你可能会对RosettaCode's Sorting algorithms/Merge sort/C++感兴趣。

Answer 3

除了索引出界的，你的问题，什么是

if (L[i] == NULL) 
    continue; 

在初始化的意义呢？

如果数组是用NULL初始化的，它不会跳过每一个元素，这看起来有点没有意义，如果至少有一个元素是NULL，这可能是偶然发生的，当你说

L[i]->population 

而且顺便说一句，最后的循环永远不会终止。