我的教授分配了一个问题,我们必须使用堆栈(或队列)来进行非递归 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);
merge(a, index, aux, lo, mid, hi);
我不确定如何解决这个问题,如有任何帮助,我们将不胜感激。我知道我必须使用 while 循环来模拟递归。但是我怎样才能拆分实际值呢?另外,如何跟踪分区值的中间值?
我真的被这个问题弄糊涂了。任何帮助,将不胜感激!
最佳答案
最重要的是了解算法的工作原理。来自 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.
解决方案 1:使用队列。
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();
}
以图形方式,
解决方案 2:使用两个堆栈
这有点复杂。
它基本上包括合并第一个堆栈的元素,将它们插入第二个堆栈,直到只剩下一个。
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();
}
以图形方式,
关于java - 将堆栈用于非递归 MergeSort?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21897184/