因此，从本质上讲，我试图了解mergesort的迭代版本。我做了一些研究，发现自下而上的mergesort是必经之路。
我的问题是我的buttom up mergesort版本不会进入它的最后一个循环(将所有内容合并在一起)。
作为示例，如果我要合并以下单词:
我会得到:
如您所知，最后2个元素未正确排序。
这是我的实现:
template <class T>
int mergesort(T arr[], int len)
{
int currSize; //current sie of subarrays to be merged
//currSize varies from 1 to n/2
int leftStart;//for picking start index of left subarray to be merged
int count = 0;//barometer
//merge subarrays in bottom up manner. First merge subarrays of size 1.
//then create sorted subarrays of size 2, then merge subarrays of size 2.
//create sorted subarrays of size 4, and so on.
for(currSize=1; currSize<=len-1; currSize = 2*currSize)
{
//picking starting point of different subarrays respective to its current size
for(leftStart=0; leftStart<len-1; leftStart+=2*currSize)
{
//find ending point of left subarray
//mid + 1 is starting point from the right
int rightEnd = Min(leftStart+2*currSize-1,len-1);
int mid = leftStart + (rightEnd - leftStart)/2;
cout << "current size = " << currSize << endl;
cout << leftStart << " + (" << rightEnd << " - " << leftStart << ") / 2 = " << mid << endl ;
//merge subarrays arr[leftStart...mid] & arr[mid+1...rightEnd]
merge(arr,leftStart,mid,rightEnd,count);
}
}
return count;
}
任何关于出问题的主意将不胜感激!
p.s这是我第一次在堆栈溢出时发帖。
最佳答案
请尝试下面的示例代码。 merge()将需要更改，以便mid和rightEnd是结束索引，而不是最后一个索引。我还删除了对count的引用，并更改了mergesort()使其不返回任何内容。
一次性分配临时数组并根据传递更改合并方向会更快。为了避免复制通过，可以在开始时确定通过的次数，如果为奇数，则第一遍可以交换成对的元素对，以便合并排序将以currSize = 2开始，并且排序后的数据将以arr结尾[]。
template <class T>
void mergesort(T arr[], int len)
{
int currSize; //current sie of subarrays to be merged
//currSize varies from 1 to n/2
int leftStart;//for picking start index of left subarray to be merged
//merge subarrays in bottom up manner. First merge subarrays of size 1.
//then create sorted subarrays of size 2, then merge subarrays of size 2.
//create sorted subarrays of size 4, and so on.
for(currSize = 1; currSize <= len; currSize = 2*currSize)
{
// picking starting point of different subarrays respective to its current size
for(leftStart = 0; leftStart < len; leftStart += 2*currSize)
{
// set mid point, break if only one run remaining
int mid = leftStart+currsize;
if(mid >= len)
break;
// set rightEnd
int rightEnd = min(mid+currSize, len);
//merge subarrays arr[leftStart...mid-1] & arr[mid...rightEnd-1]
merge(arr,leftStart,mid,rightEnd);
}
}
}
关于c++ - 自下而上的模板MergeSort迭代，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/46900525/