遞歸的內(nèi)存堆棧分析
一直對(duì)遞歸理解不深，原因是遞歸的過(guò)程很抽象，分析不清內(nèi)存堆棧的返回過(guò)程吹埠。偶然google到一篇博文遞歸(不得不說(shuō)，技術(shù)問(wèn)題還是要多google)，對(duì)遞歸過(guò)程的內(nèi)存堆棧分析豁然開(kāi)朗缘琅，下面先列出分析過(guò)程：
// A C++ program to demonstrate working of recursion
#include<bits/stdc++.h>
using namespace std;
void printFun(int test)
{
if (test < 1)
return;
else
{
cout << test << " ";
printFun(test-1); // statement 2
cout << test << " ";
return;
}
}
int main()
{
int test = 3;
printFun(test);
}
下面這個(gè)圖準(zhǔn)確的列出了整個(gè)遞歸的過(guò)程粘都，以后遇到單次遞歸問(wèn)題，完全可以用此方法分析（對(duì)于多次遞歸情況刷袍，嘗試畫(huà)了一下歸并排序里的兩次遞歸翩隧，實(shí)在沒(méi)有辦法整潔的排版，作罷呻纹。堆生。）
言歸正傳，下面分析歸并排序居暖。
歸并排序
歸并排序采用的是分治的思想顽频，首先是“分”，將一個(gè)數(shù)組反復(fù)二分為兩個(gè)小數(shù)組太闺，直到每個(gè)數(shù)組只有一個(gè)元素糯景；其次是“治”，從最小數(shù)組開(kāi)始省骂，兩兩按大小順序合并蟀淮，直到并為原始數(shù)組大小，下面是圖解：
觀察下“治”的過(guò)程钞澳，可以看出怠惶，“治”實(shí)際上是將已經(jīng)有序的數(shù)組合并為更大的有序數(shù)組。那么怎樣將已經(jīng)有序的數(shù)組合并為更大的有序數(shù)組轧粟？很簡(jiǎn)單策治，創(chuàng)建一個(gè)臨時(shí)數(shù)組C，比較A[0]兰吟，B[0]通惫，將較小值放到C[0]，再比較A[1]與B[0]（或者A[0]混蔼，B[1]）履腋，將較小值放到C[1]，直到對(duì)A惭嚣，B都遍歷一遍遵湖。可以看出數(shù)組A晚吞，B都只需遍歷一遍延旧，所以對(duì)兩個(gè)有序數(shù)組的排序的時(shí)間復(fù)雜度為O(n)。
而“分”就是將原始數(shù)組逐次二分槽地，直到每個(gè)數(shù)組只剩一個(gè)元素垄潮，一個(gè)元素的數(shù)組自然是有序的烹卒，所以就可以開(kāi)始“治”的過(guò)程了。
時(shí)間復(fù)雜度分析：分的過(guò)程需要三步：log8 = 3弯洗，而每一步都需要遍歷一次8個(gè)元素，所以8個(gè)元素共需要運(yùn)行 8log8)次指令逢勾，那么對(duì)于 n 個(gè)元素牡整，時(shí)間復(fù)雜度為 O(nlogn)。
代碼中運(yùn)用了兩次遞歸溺拱，十分抽象難懂逃贝，畫(huà)了一整頁(yè)堆棧調(diào)用圖，才弄明白（太凌亂就不貼了）迫摔，大家可以試試沐扳。
// 融合兩個(gè)有序數(shù)組，這里實(shí)際上是將數(shù)組 arr 分為兩個(gè)數(shù)組
function mergeArray(arr, first, mid, last, temp) {
let i = first;
let m = mid;
let j = mid+1;
let n = last;
let k = 0;
while(i<=m && j<=n) {
if(arr[i] < arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while(i<=m) {
temp[k++] = arr[i++];
}
while(j<=n) {
temp[k++] = arr[j++];
}
for(let l=0; l<k; l++) {
arr[first+l] = temp[l];
}
return arr;
}
// 遞歸實(shí)現(xiàn)歸并排序
function mergeSort(arr, first, last, temp) {
if(first<last) {
let mid = Math.floor((first+last)/2);
mergeSort(arr, first, mid, temp); // 左子數(shù)組有序
mergeSort(arr, mid+1, last, temp); // 右子數(shù)組有序
arr = mergeArray(arr, first, mid, last, temp);
}
return arr;
}
// example
let arr = [10, 3, 1, 5, 11, 2, 0, 6, 3];
let temp = new Array();
let SortedArr = mergeSort(arr, 0 ,arr.length-1, temp);
alert(SortedArr);
