Nicht rekursives merge sort in C ++
Frage
Ich schrieb die ganze Sache, aber ich bekomme vagee Fehler. Ich weiß nicht, was falsch ist .... ugh.Also, fragen Sie sich vielleicht, warum nicht-rekursive auch mein Lehrer es auf diese Weise für den Test hat.
void nonrec_mergesort(vector <int> & a, vector <int> & b, int s, int r)
{
int m = 1;
while (m <= r)
{
int i = 0;
while(s < (r-m))
{
stl_merge(a, b, i, ((i+i+m-1)/2), (i+m-1));
stl_merge(a, b, i+m, (min(i+2*m-1,r-1)+(i+m))/2, min(i+2*m-1,r-1));
s = s + (2*m);
}
m = m * 2;
}
}
Lösung
Dieser Link soll Ihren quetsions über Bottom-up-Mergesort beantworten, aber Sie haben nicht genügend Informationen, um leicht helfen Ihnen zur Verfügung gestellt.
http://www.algorithmist.com/index.php/Merge_sort
Input: array a[] indexed from 0 to n-1.
m = 1
while m <= n do
i = 0
while i < n-m do
merge subarrays a[i..i+m-1] and a[i+m .. min(i+2*m-1,n-1)] in-place.
i = i + 2 * m
m = m * 2
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow