c++ - C+ + - 如何打印MergeSort的所有中间步骤?

两周前,我在C 课程中被分配了一个项目,涉及向量和排序算法,我已经成功地实现了算法,并可以通过打印中间步骤和最终排序的所有向量,我的唯一问题是获取合并排序,以便将其中间结果按以下格式打印:

[14 ,7 ,3 ,12 ,9 ,11 ,6 ,2 ]

[14 ,7 ,3 ,12] [9 ,11 ,6 ,2 ]

[14 ,7] [3 ,12] [9 ,11] [6 ,2 ]

[14] [7] [3] [12] [9] [11] [6] [2 ]

[7 ,14] [3 ,12] [9 ,11] [2 ,6 ]

[3 ,7 ,12 ,14] [2 ,6 ,9 ,11 ]

[2 ,3 ,6 ,7 ,9 ,11 ,12 ,14 ]

第一行和最后一行是原始的,排序的原始向量。

以下是打印合并排序向量的步骤:


/*


 Procedure: printMergeSort


 Purpose: prints merge sort steps to the console


*/



void printMergeSort(vector <int> left, vector <int> right)


{



 for (int i = 0; i < left.size(); ++i)


 {



 if (i == 0)


 printf("[%d,", left[i]);


 else if (i < left.size() - 1)


 printf("%d,", left[i]);


 else


 printf("%d],", left[i]);



 }



 for (int i = 0; i < right.size(); ++i)


 {



 if (i == 0)


 printf("[%d,", right[i]);


 else if (i < right.size() - 1)


 printf("%d,", right[i]);


 else


 printf("%d] n", right[i]);



 }



}``



我的merge和mergesort代码:


/*


 Procedure: merge


 Purpose: Helper funcrion for mergeSort...


 Sorts the subarrays and merges them


*/



void merge(vector<int>& leftVector, vector<int>& rightVector, vector<int>& vectortoMerge)


{



 int lefttmostValue = leftVector.size();


 int rightmostValue = rightVector.size();


 int i = 0, j = 0, k = 0;



 //printMergeSort(leftVector, rightVector);



 while (j < lefttmostValue and k < rightmostValue)


 {



 if (leftVector[j] < rightVector[k])


 {



 vectortoMerge[i] = leftVector[j];


 //printf("%d", vectortoMerge[i]); 


 ++j;



 }


 else


 {



 vectortoMerge[i] = rightVector[k];



 //printf("%d", vectortoMerge[i]);


 ++k;



 }



 ++i;



 }


 while (j < lefttmostValue)


 {



 vectortoMerge[i] = leftVector[j]; 


 //printf("%d", vectortoMerge[i]);


 ++j; ++i;



 }



 while (k < rightmostValue) 


 {



 vectortoMerge[i] = rightVector[k];


 //printf("%d", vectortoMerge[i]);


 ++k; ++i;



 }



}



/*


 procedure: mergeSort


 Purpose: Main function for the merge sort algorithm....


 Splits the vector into 2 and makes a call the merge() function


*/



void mergeSort(vector<int>& vectortoSort)


{


 if (vectortoSort.size() <= 1) return;



 int middleElement = vectortoSort.size() / 2;


 vector<int> leftVector;


 vector<int> rightVector;



 for (int j = 0; j < middleElement; ++j)


 leftVector.push_back(vectortoSort[j]);


 for (int j = 0; j < (vectortoSort.size()) - middleElement; ++j)


 rightVector.push_back(vectortoSort[middleElement + j]);



 printMergeSort(leftVector, rightVector);


 printf(",");


 mergeSort(leftVector);


 mergeSort(rightVector);


 merge(leftVector, rightVector, vectortoSort);



}



上面给出了预期输出,但在输入这些值时,我得到以下结果:

[14 ,7 ,3 ,12],[9 ,11 ,6 ,2] [14 ,7],[3 ,12] [14 ,[7 ,[3 ,[12 ,[9 ,11],[6 ,2] [9,[11,[6,[2,

为了解决这个问题,有没有更好的方法?

时间:

第一个调用产生所需 [14, 7, 3, 12], [9, 11, 6, 2]将第一个递归调用应用到 [14, 7, 3, 12]完全排序那半个(递归地)之前,在第二个半部分完成之前,因此,无法产生所需 [14, 7] [3, 12] [9, 11] [6, 2]行,因为递归将继续处理 [14, 7] [3, 12]块之前的块 [9, 11] [6, 2]可以打印。

要解决这个问题,你需要完全从递归转换为广度优先遍历。

问题在于打印的索引,试试这个


printf("[");


for (int i = 0; i < left.size(); ++i)


{


 if (i != 0)


 printf(",");


 printf("%d", left[i]);


}


printf("], [");



for (int i = 0; i < right.size(); ++i)


{


 if (i != 0)


 printf(",");


 printf("%d", right[i]);


}


printf("]n");



...