0
void CensusData::mergeSort(int type) {
    if(type == 0)
        MERGE_SORT(type, 0, data.size());
}

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" << std::endl;
        //int n1;
        //int n2;
        int n1 = q - p + 1;
        int n2 = r - q;
        int L[n1 + 1];
        int R[n2 + 1];
        for(int i = 1; i < n1; i++)
        {
            cout << "filling Left Array" << endl;
            L[i] = data[p + i - 1]->population;
        }
        for(int j = 1; j < n2; j++)
        {
            cout << "filling Right Array" << endl;
            R[j] = data[q + j]->population;
        }
        int i = 1;
        int j = 1;
        for(int k = p; p < r; p++)
        {
            cout << "for loop: " << endl;
            if(L[i] <= R[j])
            {
                cout << "TRUE" << endl;
                data[k]->population = L[j];
                i = i + 1;
            }
            /*else if(data[k]->population == R[j])
            {
                cout << "FALSE" << endl;
                j = j + 1;
            }*/
            else
            {
                data[k]->population = R[j];
                j = j + 1;
            }
        }

    }
}

不用担心类型,它根本不会影响这个程序。基本上我正在尝试进行合并排序,它将采用包含整数的向量,向量如下所示:

   class Record {                         // declaration of a Record
   public:
      std::string* city;
      std::string* state;
      int population;
      Record(std::string&, std::string&, int);
      ~Record();
   };
   std::vector<Record*> data;   

基本上我一直试图让它真正排序,但它似乎根本不起作用,我什至在程序中看到了垃圾。

示例输入:237 812826 68642 输出:4484540 812826 68642

注意:程序的所有其余部分都可以正常工作(使用插入排序对其进行测试)只有这部分不起作用。

4

1 回答 1

0

看看优秀的斯坦福大学课程编程抽象的第 15 讲。它涵盖了各种类型,包括合并:

http://see.stanford.edu/see/lecturelist.aspx?coll=11f4f422-5670-4b4c-889c-008262e09e4e

您甚至可以从 SourceForge 获取源代码:

http://sourceforge.net/projects/progabstrlib/files/

于 2013-10-10T05:08:31.663 回答