使用Stacks进行非递归MergeSort? [英] Using Stacks for a Non-Recursive MergeSort?
问题描述
我的教授分配了一个问题,我们必须使用Stacks(或Queues)来创建一个非递归的MergeSort。当前代码如下:
private static void sort(Comparable [] a,int [] index,int [] aux ,int lo,int hi){
if(hi< = lo)return;
int mid = lo +(hi - lo)/ 2;
sort(a,index,aux,lo,mid);
sort(a,index,aux,mid + 1,hi);
合并(a,index,aux,lo,mid,hi);
我不知道如何处理这个问题,任何帮助都将不胜感激。我知道我必须使用while循环来模拟递归。但是,我如何分割实际值?另外,如何跟踪分区值的中间位置?
我真的很困惑这个问题。任何帮助,将不胜感激!
最重要的是要了解算法的工作原理。来自
my professor assigned a problem in which we must use Stacks (or Queues) to make a non-recursive MergeSort. The current code is as follows:
private static void sort(Comparable[] a, int[] index, int[] aux, int lo, int hi) {
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, index, aux, lo, mid);
sort(a, index, aux, mid + 1, hi);
merge(a, index, aux, lo, mid, hi);
I'm not sure how to approach this problem, and any help would be appreciated. I know that i must use a while loop to emulate the recursion. But how can I split the actual values? Also, how can I keep track of the middle of the partitioned values?
I am really confused by the problem. Any help would be appreciated!
The most important thing is to understand how the algorithm works. From Wikipedia:
Conceptually, a merge sort works as follows:
Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted). Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.
Solution 1: With a queue.
static int[] mergeSortQueue(int[] A) {
Queue<int[]> queue = new LinkedList<int[]>();
for (int i = 0; i < A.length; i++)
{
queue.add(new int[]{A[i]});
}
while (queue.size()>1)
{
int[] r = queue.poll();
int[] l = queue.poll();
int[] merged=merge(l, r);
queue.add(merged);
}
return queue.poll();
}
Graphically,
Solution 2: With two stacks
This is a bit more complex.
It basically consists on merging the elements of the first stack, inserting them into the second stack, until only one remains.
static int[] mergeSortStacks(int[] A) {
Stack<int[]> stack = new Stack<int[]>();
Stack<int[]> stack2 = new Stack<int[]>();
for (int i = 0; i < A.length; i++)
{
stack.push(new int[]{A[i]});
}
while (stack.size()>1)
{
while (stack.size()>1)
{
int[] r = stack.pop();
int[] l = stack.pop();
int[] merged=merge(l, r);
stack2.push(merged);
}
while (stack2.size()>1)
{
int[] r = stack2.pop();
int[] l = stack2.pop();
int[] merged=merge(l, r);
stack.push(merged);
}
}
return stack.isEmpty() ? stack2.pop() : stack.pop();
}
Graphically,
这篇关于使用Stacks进行非递归MergeSort?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!