宿州高端网站建设,轻松筹 的网站价格做,网站建设期末考试,网站备案个人好还是企业好1. 递归 在众多排序算法中#xff0c;归并排序#xff08;Merge Sort#xff09;和快速排序#xff08;Quick Sort#xff09;都是时间复杂度为 O(nlog2n) 的高效排序。 这两种排序有一种共性#xff0c;就是运用到了递归的思想。 在程序设计中#xff0c;递归是一个很有…1. 递归 在众多排序算法中归并排序Merge Sort和快速排序Quick Sort都是时间复杂度为 O(nlog2n) 的高效排序。 这两种排序有一种共性就是运用到了递归的思想。 在程序设计中递归是一个很有用的性质用递归写出来的算法一般来说都很简洁明了易于理解。 例如归并排序 public final class MergeSort extends BasicMergeSort {Overridepublic void sort(int[] array) {sort(array, 0, array.length - 1);}private void sort(int[] array, int left, int right) {if (left right) {int mid ArrayHelper.getMiddle(left, right);sort(array, left, mid);sort(array, mid 1, right);mergeSolution.merge(array, left, right);}}
}其中mergeSolution.merge() 是将两个有序数组合并成一个有序数组的接口详细内容可以参见 https://www.cnblogs.com/jing-an-feng-shao/p/9038915.html 然而漂亮的代码与高效的代码往往是相冲的。递归存在一个很致命的缺点。 众所周知Java 程序中的数据存放在堆栈Stack空间中堆栈具有访问效率高速度快的优点但同时其分配的空间往往是有限的。 在递归过程中会把上层的数据不断地压入堆栈空间中。如果递归地深度过大在达到递归的结束条件之前堆栈中的数据已经溢出那么就会导致程序崩溃。 StackOverFlow 这个异常相信读者见到的次数不在少数。 2. 递归转循环 所以在这种情况下往往就需要将递归结构转化为循环结构去解决问题。 那么怎么进行转化呢这时候就要从递归的本质出发。 递归是什么它是 数据的传递 数据的压栈。 所以解决了怎么传递数据的问题和怎么数据压栈的问题就能将递归转化为循环那么自然而然地想到了 记录传递的数据 - 利用自定义对象 Record 记录传递的数据。利用堆栈的结构 - 利用程序手动将 StackRecord 进行压栈的操作。最后通过迭代自定义的堆栈内数据达到递归地效果。 3. 归并排序的非递归实现 首先需要明确的一点是归并排序在递归地过程中传递什么数据 显然是两个子数组的左、中、右节点其中中节点时刻已通过计算得出的可有可无。 那么我们现在就可以设计对象 Record为方便使用这里记录了中节点 private static class Record {int left;int mid;int right;private Record(int left, int mid, int right) {this.left left;this.mid mid;this.right right;}}其次如何将 Record 显示地入栈 假设现在我们正在进行长度为 8 的数组排序那么显然我们最终希望堆栈中的数据是这样的方便起见这里的 Record 不计中节点 这样的堆栈结构自上而下进行合并就是我们期望的归并排序的合并顺序。 这样的结构是不是很眼熟 没错看到这个图我们很自然地会想到 汉诺塔Tower of Hanoi。 那么又是很自然地除了目标堆栈还需要申请另外 2 个辅助空间去完成压栈工作。 方便起见这里的辅助空间也使用堆栈结构。 所以现在就有了初始堆栈 stack1目标堆栈 stack2中转堆栈 stack3。 将原始数组压入 stack1。将 stack1 中的数据全部取出放入 stack3。依次取出 stack3 中的 Record压入 stack2同时判断 left mid若是将 Record(left, mid) 压入 stack1判断 mid1 right若是将 Record(mid1, right) 压入stack1。若 stack1 中仍有数据循环步骤 2、3。若 stack1 已经清空表明 stack2 已经满足上图结构即全部数据已经压入 stack2 中循环归并 stack2 中的记录直至 stack2 清空。 于是有如下代码 public class MergeSortLoop extends BasicMergeSort {private static final StackRecord stack1 new Stack();private static final StackRecord stack2 new Stack();private static final StackRecord stack3 new Stack();Overridepublic void sort(int[] array) {int left 0;int right array.length - 1;pushStack(stack1, left, right);while (!stack1.isEmpty()) {popAll(stack1, stack3);while (!stack3.isEmpty()) {Record record stack3.pop();stack2.push(record);if (record.left record.mid) {pushStack(stack1, record.left, record.mid);}if (record.mid 1 record.right) {pushStack(stack1, record.mid 1, record.right);}}}while (!stack2.isEmpty()) {Record toBeMerged stack2.pop();mergeSolution.merge(array, toBeMerged.left, toBeMerged.right);}}private void popAll(StackRecord source, StackRecord target) {while (!source.isEmpty()) {target.push(source.pop());}}private void pushStack(StackRecord stack, int left, int right) {Record record new Record(left, ArrayHelper.getMiddle(left, right), right);stack.push(record);}private static class Record {int left;int mid;int right;private Record(int left, int mid, int right) {this.left left;this.mid mid;this.right right;}}
} 4. 另一种堆栈模型 将递归结构转为循环结构核心思想就是构建堆栈模型。 之前写到的这种 类-汉诺塔 堆栈模型其结构非常漂亮但是构造效率却相对较低其中需要用到 2 个额外的辅助空间更多的入栈-出栈操作。 其实仔细回想归并排序的递归过程并不是依从这种 类-汉诺塔 堆栈模型的顺序去递归的其递归过程类似以下堆栈模型 构造这种堆栈结构只需要初始堆栈 stack1目标堆栈 stack2。 将原始数组压入 stack1。取出 stack1 栈顶数据放入 stack2。根据取出的数据 record判断 left mid若是将 Record(left, mid) 压入 stack1判断 mid1 right若是将 Record(mid1, right) 压入stack1。若 stack1 中仍有数据循环步骤 2、3。若 stack1 已经清空表明 stack2 已经满足上图结构即全部数据已经压入 stack2 中循环归并 stack2 中的记录直至 stack2 清空。 与之前的过程相比唯一的变化就在于第 2 步只需要取出栈顶数据而不是堆栈 stack1 中的所有数据。 转载于:https://www.cnblogs.com/jing-an-feng-shao/p/9084928.html
