我正在尝试为家庭作业实现合并排序，我们应该这样做，因此它与此伪代码非常相似（假设数组以 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 是整个数组， pq 和 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;