非递归归并排序有两个嵌套循环 - 怎么样？ [英] Non-recursive merge sort with two nested loops - how?
问题描述
在这里第一个问题，是的，这是一个家庭作业的问题。我们的任务是一个数组（我熟悉的）上进行归并排序，但在某种程度上，我不确定该怎么做。通常我将有一个单独的合并和合并排序的功能，并使用两种。然而，这听起来像他希望一切都在一个方法？我只是希望，也许有人可以帮助明确的事情了我，或把它们放到方面，我可以更好地了解。
First question here, and yes this is a homework question. We are tasked with performing merge sort on an array (which I am familiar with), but in a way I am unsure of how to do. Usually I would have a separate merge and merge sort function, and use the two. However, it sounds like he wants everything in one method? I was just hoping maybe someone could help clear things up for me, or put them into terms I can better understand.
从分配：
您需要实现的合并排序的非递归版本 算法。安排两个嵌套的循环来完成这个任务。外 循环应该用于合并提供的段的大小。内环 应选择部分职位的照顾。内环 应开始于左边缘并移动段到右侧。 排列左变量，中，右适当的值，从而使 排序只是通过遍历呼叫完成 合并（A，左，中，右）。
you will need to implement a non-recursive version of merge-sort algorithm. Arrange two nested loops to accomplish this task. The outer loop should provide the size of segments for merging. The inner loop should take care of selecting positions of segments. The inner loop should start at the left edge and move your segments to the right. Arrange appropriate values of variables left, middle, right, so that sorting is accomplished just by iterating the call merge(a,left,middle,right).
我讨厌这么模糊，但我真的不明白，任何的他在说什么。首先，何谓外环应提供段的大小？如何做一个循环的为的东西吗？那么下一句 - 这是什么，他用段是什么意思？数据？
I hate to be so vague, but I really don't understand any of what he's saying. First, what is meant by "outer loop should provide the size of segments"? How does a loop provide anything? What about the next sentence - what does he mean by segments? The data?
我不要求为code，但任何伪code将是非常有益的。
I'm not asking for code, but any psuedocode would be really helpful.
如果任何人都可以尝试，并破译了他的意思，我想AP preciate它。我已经给他发邮件吧，但它已经几个小时，我还没有收到回音。
If anyone could try and decipher what he means, I'd appreciate it. I've already emailed him about it, but it's been a few hours and I've yet to hear back.
感谢您！
推荐答案
这不是那么困难。考虑递归合并：
It's not so difficult. Consider the recursive merge:
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
/ \ split
+-+-+-+-+ +-+-+-+-+
| | | | | | | | | |
+-+-+-+-+ +-+-+-+-+
/ \ / \ split
+-+-+ +-+-+ +-+-+ +-+-+
| | | | | | | | | | | |
+-+-+ +-+-+ +-+-+ +-+-+
/ \ / \ / \ / \ split
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
| | | | | | | | | | | | | | | |
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
\ / \ / \ / \ / merge
+-+-+ +-+-+ +-+-+ +-+-+
| | | | | | | | | | | |
+-+-+ +-+-+ +-+-+ +-+-+
\ / \ / merge
+-+-+-+-+ +-+-+-+-+
| | | | | | | | | |
+-+-+-+-+ +-+-+-+-+
\ / merge
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
如果您发现，当你拆，你没有做任何事情。您只需告诉递归函数到数组部分排序。排序的阵列由第一分拣两半，然后合并它。所以基本上，你所拥有的是这样的：
If you notice, when you split, you don't really do anything. You just tell the recursive function to partially sort the array. Sorting the array consists of first sorting both halves and then merging it. So basically, what you have is this:
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
| | | | | | | | | | | | | | | |
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
\ / \ / \ / \ / merge
+-+-+ +-+-+ +-+-+ +-+-+
| | | | | | | | | | | |
+-+-+ +-+-+ +-+-+ +-+-+
\ / \ / merge
+-+-+-+-+ +-+-+-+-+
| | | | | | | | | |
+-+-+-+-+ +-+-+-+-+
\ / merge
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
现在从这里应该是显而易见的。你先合并阵列2元2，然后4乘4，然后8×8等，这是外部的为为您提供了2，4，8，16， 32，...（这是它所谓的段的，因为我循环包含该号码的大小）和内为（说与迭代器Ĵ）越过阵列，我通过我合并阵列[J ... J + I / 2-1] 与阵列[J + I / 2..j + I-1] 。
Now from here it should be obvious. You first merge elements of the array 2 by 2, then 4 by 4, then 8 by 8 etc. That is the outer for gives you 2, 4, 8, 16, 32, ... (which is what it calls size of the segment because the i of the loop contains that number) and the inner for (say with iterator j) goes over the array, i by i merging array[j...j+i/2-1] with array[j+i/2..j+i-1].
我不会写的code，因为这是功课。
I wouldn't write the code since this is homework.
编辑：的图片是如何内为和
试想一下，如果我 4，让你在这个阶段：
Imagine if i is 4, so you are at this stage:
+-+-+ +-+-+ +-+-+ +-+-+
| | | | | | | | | | | |
+-+-+ +-+-+ +-+-+ +-+-+
\ / \ / merge
+-+-+-+-+ +-+-+-+-+
| | | | | | | | | |
+-+-+-+-+ +-+-+-+-+
您有一个为，一旦给你 0 （即 0 *我）的Ĵ然后 4 （即 1 * I ）的Ĵ。 （如果我为2，你会Ĵ要像0，2，4，6）
you will have a for that once gives you 0(which is 0*i) as j and then 4 (which is 1*i) as j. (if i was 2, you would have j going like 0, 2, 4, 6)
现在，当你需要合并数组[0..1] 与数组[2..3] （这是由阵列[J + I / 2..j + I-1] 与 J = 0 ），然后数组[4..5] 与数组[6..7] （这是由同样的公式阵列[J ... J + I / 2-1]制定和阵列[J + I / 2..j + I-1] 因为现在 J = 4 ），即：
Now, once you need to merge array[0..1] with array[2..3] (which is formulated by array[j..j+i/2-1] and array[j+i/2..j+i-1] with j = 0) and then array[4..5] with array[6..7] (which is formulated by the same formulas array[j...j+i/2-1] and array[j+i/2..j+i-1] because now j = 4) That is:
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
希望这是明显的至少有一点。
Hope this is clear at least a little.
侧帮：只是，如果你真的不知道有一丝如何为和
Side help: Just a hint if you don't really know how for works:
for (statement1; condition; statement2)
{
// processing
}
是这样写
statement1;
while (condition)
{
// processing
statement2;
}
所以，如果你总是写了
So, if you always wrote
for (int i = 0; i < 10; ++i)
这意味着从0开始，而我小于10时，做一些与我，然后加一。现在，如果你想要我来改变不同的，你只需要修改语句2 如：
it meant starting from 0, while i is smaller than 10, do something with i and then increment it. Now if you want i to change differently, you just change statement2 such as:
for (int i = 1; i < 1024; i *= 2)
（试着了解这最后为作品是根据它的等效，而，我给你写了）
(Try to understand how that final for works based on its equivalent while that I wrote you)
这篇关于非递归归并排序有两个嵌套循环 - 怎么样？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
