用两个嵌套循环进行递归合并排序
这里的第一个问题，是的，这是一个家庭作业问题。 我们负责在一个数组上执行合并排序（我熟悉这个数组），但以某种方式，我不确定如何去做。 通常我会有一个单独的合并和合并排序功能，并使用这两个。 然而，这听起来像他希望在一种方法中的一切？ 我只是希望也许有人能帮我解决问题，或者把它们放到我能更好理解的地方。
来自作业：
您将需要实现合并排序算法的非递归版本。 排列两个嵌套循环来完成此任务。 外部循环应提供合并的分段大小。 内部循环应该照顾选择段的位置。 内部循环应该从左边缘开始，并将您的部分向右移动。 排列左，中，右变量的适当值，以便通过迭代调用合并（a，left，middle，right）来完成排序。
我讨厌这么模糊，但我真的不明白他在说什么。 首先，“外环应该提供细分的大小”是什么意思？ 循环如何提供任何东西？ 那么下一句怎么样 - 他的分段是什么意思？ 数据？
我没有要求代码，但任何伪代码都会很有帮助。
如果有人能够试图破译他的意思，我会很感激。 我已经发邮件给他了，但已经过了几个小时，我还没有收到回复。
谢谢！
这并不难。 考虑递归合并：
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
/ split
+-+-+-+-+ +-+-+-+-+
| | | | | | | | | |
+-+-+-+-+ +-+-+-+-+
/ / split
+-+-+ +-+-+ +-+-+ +-+-+
| | | | | | | | | | | |
+-+-+ +-+-+ +-+-+ +-+-+
/ / / / split
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
| | | | | | | | | | | | | | | |
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
/ / / / merge
+-+-+ +-+-+ +-+-+ +-+-+
| | | | | | | | | | | |
+-+-+ +-+-+ +-+-+ +-+-+
/ / merge
+-+-+-+-+ +-+-+-+-+
| | | | | | | | | |
+-+-+-+-+ +-+-+-+-+
/ merge
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
如果你注意到，当你分裂时，你什么也没有做。 你只要告诉递归函数对数组进行部分排序。 对数组进行排序包括首先对两半进行排序然后合并它。 所以基本上，你拥有的是这样的：
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
| | | | | | | | | | | | | | | |
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
/ / / / merge
+-+-+ +-+-+ +-+-+ +-+-+
| | | | | | | | | | | |
+-+-+ +-+-+ +-+-+ +-+-+
/ / merge
+-+-+-+-+ +-+-+-+-+
| | | | | | | | | |
+-+-+-+-+ +-+-+-+-+
/ merge
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
现在从这里应该是显而易见的。 您首先由2合并阵列2的元素，4乘4，然后，再由8等8也就是说外for给你2，4，8，16，32，...（这是它所称的大小段，因为i循环的包含该号码）和所述内for （与迭代说j ）变为在阵列上， i通过i合并array[j...j+i/2-1]与array[j+i/2..j+i-1] 。
我不会写代码，因为这是作业。
编辑：如何内的图片for作品
想象一下，如果i是4，那么你处于这个阶段：
+-+-+ +-+-+ +-+-+ +-+-+
| | | | | | | | | | | |
+-+-+ +-+-+ +-+-+ +-+-+
/ / merge
+-+-+-+-+ +-+-+-+-+
| | | | | | | | | |
+-+-+-+-+ +-+-+-+-+
你将有一个for ，一旦给你0 （这是0*i ），为j然后4 （其为1*i ）作为j 。 （如果i是2，则必须j去像0，2，4，6）
现在，一旦你需要合并array[0..1]和array[2..3] （它由array[j..j+i/2-1]和array[j+i/2..j+i-1]与j = 0 ），然后array[4..5]与array[6..7] （由相同的公式array[j...j+i/2-1]和array[j+i/2..j+i-1]因为现在j = 4 ）即：
i = 4:
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
^ ^ ^ ^ ^ ^ ^ ^
| | | | | | | |
/ / / /
(j = 0) (j = 4)
| | | | | | | |
j | | | j | | |
| | | j+i-1 | | | j+i-1
| | j+i/2 | | j+i/2
| j+i/2-1 | j+i/2-1
| | | | | | | |
| | | | | | | |
/ / / /
v v v v
merge merge
希望这至少有一点清楚。
侧帮：只是一个提示，如果你真的不知道该怎么for作品：
for (statement1; condition; statement2)
{
// processing
}
就像写作一样
statement1;
while (condition)
{
// processing
statement2;
}
所以，如果你总是写
for (int i = 0; i < 10; ++i)
它意味着从0开始，而i小于10，对i做些什么，然后增加它。 现在，如果你想让i改变不同的方式，你只需改变statement2例如：
for (int i = 1; i < 1024; i *= 2)
（试着了解这最后for作品基于其等效while我写你）
这是我使用std::merge的惰性迭代/自底向上合并排序实现：
template<class InIt, class OutIt>
OutIt mergesort(InIt begin, InIt const end, OutIt o /* auxiliary buffer */)
{
ptrdiff_t j;
for (j = 0; begin != end; ++begin, ++j)
{
for (ptrdiff_t n = 1; n <= j && j % (n * 2) == 0; n *= 2)
{
o = std::merge(o - n * 2, o - n, o - n, o, begin - n * 2);
o = std::swap_ranges(begin - n * 2, begin, o - n * 2);
}
*o = *begin;
++o;
}
--j;
for (ptrdiff_t m = 1, n = 1; n <= j; n *= 2)
{
if (j & n)
{
o = std::merge(o - (m + n), o - m, o - m, o, o - (m + n));
o = std::swap_ranges(begin - (m + n), begin, o - (m + n));
m += n;
}
}
return o;
}
这是一个使用std::inplace_merge的就地版本：
template<class InIt>
InIt inplace_mergesort(InIt begin, InIt const end)
{
ptrdiff_t j;
for (j = 0; begin != end; ++begin, ++j)
{
for (ptrdiff_t n = 1; n <= j && j % (n * 2) == 0; n *= 2)
{ std::inplace_merge(begin - n * 2, begin - n, begin); }
}
--j;
for (ptrdiff_t m = 1, n = 1; n <= j; n *= 2)
{
if (j & n)
{
std::inplace_merge(begin - (m + n), begin - m, begin);
m += n;
}
}
return begin;
}
这里是自下而上的mergesort的C＃版本（更多的细节可以参考我的博客@ http://dream-er.blogspot.com/2014/07/mergesort-arrays-and-lists.html）
void BottomUpMergesort(int[] a)
{
int[] temp = new int[a.Length];
for (int runWidth = 1; runWidth < a.Length; runWidth = 2 * runWidth)
{
for (int eachRunStart = 0; eachRunStart < a.Length;
eachRunStart = eachRunStart + 2 * runWidth)
{
int start = eachRunStart;
int mid = eachRunStart + (runWidth - 1);
if(mid >= a.Length)
{
mid = a.Length - 1;
}
int end = eachRunStart + ((2 * runWidth) - 1);
if(end >= a.Length)
{
end = a.Length - 1;
}
this.Merge(a, start, mid, end, temp);
}
for (int i = 0; i < a.Length; i++)
{
a[i] = temp[i];
}
}
合并被定义为：
void Merge(int[] a, int start, int mid, int end, int[] temp)
{
int i = start, j = mid+1, k = start;
while((i<=mid) && (j<=end))
{
if(a[i] <= a[j])
{
temp[k] = a[i];
i++;
}
else
{
temp[k] = a[j];
j++;
}
k++;
}
while(i<=mid)
{
temp[k] = a[i];
i++;
k++;
}
while (j <= end)
{
temp[k] = a[j];
j++;
k++;
}
Assert.IsTrue(k == end+1);
Assert.IsTrue(i == mid+1);
Assert.IsTrue(j == end+1);
}
}
这里仅供参考TopDownMergesort：
void TopDownMergesort(int[] a, int[] temp, int start, int end)
{
if(start==end)
{
//run size of '1'
return;
}
int mid = (start + end) / 2;
this.TopDownMergesort(a, temp, start, mid);
this.TopDownMergesort(a, temp, mid + 1, end);
this.Merge(a, start, mid, end, temp);
for(int i = start;i<=end;i++)
{
a[i] = temp[i];
}
}
单元测试
[TestMethod]
public void BottomUpMergesortTests()
{
int[] a = { 13, 4, 1, 3, 8, 11, 9, 10 };
this.BottomUpMergesort(a);
int[] b = { 1, 3, 4, 8, 9, 10, 11, 13 };
Assert.IsTrue(a.Length == b.Length);
for (int i = 0; i < a.Length; i++)
{
Assert.IsTrue(a[i] == b[i]);
}
List<int> l = new List<int>();
for (int i = 10; i >= 1; i--)
{
l.Add(i);
}
var la = l.ToArray();
this.BottomUpMergesort(la);
for (int i = 1; i <= 10; i++)
{
Assert.IsTrue(la[i - 1] == i);
}
l.Clear();
for (int i = 16; i >= 1; i--)
{
l.Add(i);
}
la = l.ToArray();
this.BottomUpMergesort(la);
for (int i = 1; i <= l.Count; i++)
{
Assert.IsTrue(la[i - 1] == i);
}
}