排序算法杂谈（三） —— 归并排序的非递归实现
1. 遞歸
?
在眾多排序算法中，歸并排序（Merge Sort）和快速排序（Quick Sort）都是時間復(fù)雜度為 O(nlog2n) 的高效排序。
這兩種排序有一種共性，就是運用到了遞歸的思想。
?
在程序設(shè)計中，遞歸是一個很有用的性質(zhì)，用遞歸寫出來的算法，一般來說都很簡潔明了，易于理解。
例如歸并排序：
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() 是將兩個有序數(shù)組合并成一個有序數(shù)組的接口，詳細內(nèi)容可以參見：
https://www.cnblogs.com/jing-an-feng-shao/p/9038915.html
?
然而，漂亮的代碼與高效的代碼往往是相沖的。遞歸存在一個很致命的缺點。
眾所周知，Java 程序中的數(shù)據(jù)，存放在堆棧（Stack）空間中，堆棧具有訪問效率高，速度快的優(yōu)點，但同時其分配的空間往往是有限的。
在遞歸過程中，會把上層的數(shù)據(jù)不斷地壓入堆棧空間中。如果遞歸地深度過大，在達到遞歸的結(jié)束條件之前，堆棧中的數(shù)據(jù)已經(jīng)溢出，那么就會導(dǎo)致程序崩潰。
StackOverFlow 這個異常，相信讀者見到的次數(shù)不在少數(shù)。
?
?
2. 遞歸轉(zhuǎn)循環(huán)
?
所以，在這種情況下，往往就需要將遞歸結(jié)構(gòu)轉(zhuǎn)化為循環(huán)結(jié)構(gòu)去解決問題。
那么，怎么進行轉(zhuǎn)化呢？這時候就要從遞歸的本質(zhì)出發(fā)。
?
遞歸是什么？它是?數(shù)據(jù)的傳遞 + 數(shù)據(jù)的壓棧。
所以解決了怎么傳遞數(shù)據(jù)的問題和怎么數(shù)據(jù)壓棧的問題，就能將遞歸轉(zhuǎn)化為循環(huán)，那么自然而然地想到了：
- 記錄傳遞的數(shù)據(jù) -> 利用自定義對象 Record 記錄傳遞的數(shù)據(jù)。
- 利用堆棧的結(jié)構(gòu) -> 利用程序手動將 Stack<Record> 進行壓棧的操作。
最后，通過迭代自定義的堆棧內(nèi)數(shù)據(jù)，達到遞歸地效果。
?
?
3. 歸并排序的非遞歸實現(xiàn)
?
首先需要明確的一點，是歸并排序在遞歸地過程中傳遞什么數(shù)據(jù)？
顯然是兩個子數(shù)組的左、中、右節(jié)點，其中中節(jié)點時刻已通過計算得出的，可有可無。
那么我們現(xiàn)在就可以設(shè)計對象 Record（為方便使用，這里記錄了中節(jié)點）：
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 顯示地入棧？
假設(shè)現(xiàn)在我們正在進行長度為 8 的數(shù)組排序，那么顯然，我們最終希望堆棧中的數(shù)據(jù)是這樣的（方便起見，這里的 Record 不計中節(jié)點）：
?
?
這樣的堆棧結(jié)構(gòu)，自上而下進行合并，就是我們期望的歸并排序的合并順序。
這樣的結(jié)構(gòu)是不是很眼熟？
沒錯，看到這個圖，我們很自然地會想到 漢諾塔（Tower of Hanoi）。
那么又是很自然地，除了目標(biāo)堆棧，還需要申請另外 2 個輔助空間去完成壓棧工作。
方便起見，這里的輔助空間也使用堆棧結(jié)構(gòu)。
所以現(xiàn)在就有了：初始堆棧 stack1，目標(biāo)堆棧 stack2，中轉(zhuǎn)堆棧 stack3。
?
?
于是，有如下代碼：
public class MergeSortLoop extends BasicMergeSort {private static final Stack<Record> stack1 = new Stack();private static final Stack<Record> stack2 = new Stack();private static final Stack<Record> 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(Stack<Record> source, Stack<Record> target) {while (!source.isEmpty()) {target.push(source.pop());}}private void pushStack(Stack<Record> 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. 另一種堆棧模型
將遞歸結(jié)構(gòu)轉(zhuǎn)為循環(huán)結(jié)構(gòu)，核心思想就是構(gòu)建堆棧模型。
之前寫到的這種 類-漢諾塔 堆棧模型，其結(jié)構(gòu)非常漂亮，但是構(gòu)造效率卻相對較低（其中需要用到 2 個額外的輔助空間，更多的入棧-出棧操作）。
其實，仔細回想歸并排序的遞歸過程，并不是依從這種 類-漢諾塔 堆棧模型的順序去遞歸的，其遞歸過程類似以下堆棧模型：
?
?
?
構(gòu)造這種堆棧結(jié)構(gòu)，只需要初始堆棧 stack1，目標(biāo)堆棧 stack2。
?
與之前的過程相比，唯一的變化就在于第 2 步，只需要取出棧頂數(shù)據(jù)，而不是堆棧 stack1 中的所有數(shù)據(jù)。
?
轉(zhuǎn)載于:https://www.cnblogs.com/jing-an-feng-shao/p/9084928.html
總結(jié)
以上是生活随笔為你收集整理的排序算法杂谈（三） —— 归并排序的非递归实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Android 实时数据库工具Datab
- 下一篇： echarts我常用的参数总结