題目
設(shè)計(jì)一個(gè)算法可將{4, 2, -3, 6, 1} （或其他亂序的數(shù)組）按升序排序得到 {-3, 1, 2, 4, 6}搪泳。
解題思路
1.將數(shù)組分成兩組
2.每一組各自排序吨掌，怎么排?用同樣的方法排丐枉，重復(fù)動(dòng)作(1)分成兩組...（遞歸）
3.合并：經(jīng)過(guò)1盟萨，2動(dòng)作的遞歸后岔绸，最后會(huì)變成一顆樹(shù)蔽莱，再?gòu)臉?shù)的最底層開(kāi)始每?jī)蓚€(gè)節(jié)點(diǎn)開(kāi)始合并, 合并的同時(shí)做好排序逛万，當(dāng)合并到最頂層時(shí)整個(gè)數(shù)組就排序好了泳猬。
如何排序：每個(gè)節(jié)點(diǎn)的數(shù)據(jù)都是由上一次合并后得到的是排序好的！我們可以把兩個(gè)節(jié)點(diǎn)想象為有兩個(gè)數(shù)組宇植，每次對(duì)比兩個(gè)數(shù)組的第一個(gè)元素取出較小的元素放到另一個(gè)數(shù)組里得封，當(dāng)兩個(gè)數(shù)組的元素都被取完了就完成排序和合并了。
(1),(2)
(3)
(排序合并)
Code
public void mergeSort(int[] arr) {
if (arr == null || arr.length <= 1) return;
int[] helper = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, helper);
}
// 1.將數(shù)組分成兩組
// 2.每一組各自排序指郁，怎么排?用同樣的方法排忙上，重復(fù)動(dòng)作(1)分成兩組...（遞歸）
private void mergeSort(int[] arr, int left, int right, int[] helper) {
//base case:如果節(jié)點(diǎn)只剩下一個(gè)元素了則停止分裂
if (left >= right) {
return;
}
//防止大數(shù)溢出,如果left和right都等于Integer.MAX_VALUE那么它們相加就會(huì)超出int的取值范圍導(dǎo)致溢出
int mid = left + (right - left) / 2;
//分組
mergeSort(arr, left, mid, helper);
mergeSort(arr, mid + 1, right, helper);
//合并
megre(arr, left, mid, right, helper);
}
//3.合并：經(jīng)過(guò)1，2動(dòng)作的遞歸后闲坎，最后會(huì)變成一顆樹(shù)晨横，再?gòu)臉?shù)的最底層開(kāi)始每?jī)蓚€(gè)節(jié)點(diǎn)開(kāi)始合并,
// 合并的同時(shí)做好排序洋腮，當(dāng)合并到最頂層時(shí)整個(gè)數(shù)組就排序好了。
// 如何排序：每個(gè)節(jié)點(diǎn)的數(shù)據(jù)都是由上一次合并后得到的是排序好的手形！
// 我們可以把兩個(gè)節(jié)點(diǎn)想象為有兩個(gè)數(shù)組，每次對(duì)比兩個(gè)數(shù)組的第一個(gè)元素取出較小的元素放到另一個(gè)數(shù)組里悯恍，
// 當(dāng)兩個(gè)數(shù)組的元素都被取完了就完成和排序和合并了库糠。
private void megre(int[] arr, int left, int mid, int right, int[] helper) {
for (int i = 0; i < arr.length; i++) {
helper[i] = arr[i];
}
int l = left;//表示左邊數(shù)組的指針
int r = mid + 1;//表示右邊數(shù)組的指針
int k = left;//存放排好序的元素的數(shù)組的指針
while (l <= mid && r <= right) {//當(dāng)有其中一個(gè)指針先走完則停止while循環(huán)
if (helper[l] < helper[r]) {
arr[k] = helper[l];//取出較小的元素放到另一個(gè)數(shù)組里
k++;//指針右移
l++;//指針右移
} else {
arr[k] = helper[r];//取出較小的元素放到另一個(gè)數(shù)組里
k++;//指針右移
r++;//指針右移
}
}
//如果r指針先走完l指針還未走完則直接將元素放到另一個(gè)數(shù)組的尾部
while (l <= mid) {
arr[k++] = helper[l++];
}
}
時(shí)空復(fù)雜度分析
時(shí)間復(fù)雜度：
Merge sort的時(shí)空復(fù)雜度分析比較復(fù)雜，我們可以把這個(gè)算法的執(zhí)行過(guò)程分為兩個(gè)階段來(lái)看:
第一個(gè)階段：分組
從這張圖中我們可以看出分組時(shí)的每一層的節(jié)點(diǎn)數(shù)都是上一層的double,所以總共的節(jié)點(diǎn)數(shù)是:1+2+4+8+...+n/2 = 1+1+2+4+8+...+n/2-1 = n/2 + n/2 -1 = n-1,忽略對(duì)復(fù)雜度影響較小的系數(shù)所以總節(jié)點(diǎn)是n涮毫，而且每次分組只執(zhí)行了一行求mid的代碼:
int mid = left + (right - left) / 2;也就是O(1), 所以第一階段的時(shí)間復(fù)雜度是O(n*1) = O(n);
第二階段：合并
我們來(lái)看看合并的核心代碼
while (l <= mid && r <= right) {
if (helper[l] < helper[r]) {
arr[k] = helper[l];
k++;
l++;
} else {
arr[k] = helper[r];
k++;
r++;
}
}
是一個(gè)while循環(huán)瞬欧，隨著arr數(shù)組的長(zhǎng)度的增加while循環(huán)的次數(shù)是線性增長(zhǎng)的所以我們得出這段代碼的復(fù)雜度是O(n), 其實(shí)只要是while循環(huán)或者單層for循環(huán)我們都可以認(rèn)為復(fù)雜度就是O(n)，既然每一層的復(fù)雜度是O(n)那么我們只要算出總共有多少層就可以算出第二階段的時(shí)間復(fù)雜度罢防，如上圖我們假設(shè)這是一棵滿的二叉樹(shù)那么就總共有l(wèi)og2n層艘虎，或者假設(shè)數(shù)組的長(zhǎng)度n=8每次二分總共可以分裂log2n次，所以第二階段的時(shí)間復(fù)雜度是O(nlgn). （lgn = log2n）
結(jié)論：所以merge sort的時(shí)間復(fù)雜度是O(n)+O(nlgn),因?yàn)槲覀冴P(guān)心的是漸進(jìn)性復(fù)雜度有高次項(xiàng)在的時(shí)候可以忽略低次項(xiàng)咒吐，所以O(shè)(n)<O(nlgn)取O(nlgn)野建。
空間復(fù)雜度：
因?yàn)槭莔egre sort是遞歸實(shí)現(xiàn)的，所以空間復(fù)雜度與其遞歸的層數(shù)相關(guān)恬叹，先普及一個(gè)概念: 在java中每一個(gè)函數(shù)的開(kāi)始和結(jié)束都代表著在JVM Stack中一個(gè)棧幀(stack frame)的入棧和出棧候生，遞歸是函數(shù)自己調(diào)用自己，每次調(diào)用自己都會(huì)往JVM Stack中壓入一個(gè)stack frame
因?yàn)閙egre sort的遞歸樹(shù)總共有l(wèi)gn層绽昼，所以我們最多時(shí)使用了lgn個(gè)stack frame唯鸭，so空間復(fù)雜度是O(lgn)。
但是我們這段merge sort代碼的空間復(fù)雜度并不是O(lgn)而是O(n),
為什么呢硅确？因?yàn)槲覀兂吮仨氁褂玫降木植孔兞客膺€創(chuàng)建了一個(gè)輔助我們計(jì)算的數(shù)組int[] helper = new int[arr.length]; 目溉，所以空間復(fù)雜度應(yīng)該是：O(lgn)+O(n)而O(lgn)<O(n), 所以我們megre sort的空間復(fù)雜度是O(n)。(我們關(guān)心的是漸進(jìn)性復(fù)雜度有高次項(xiàng)在的時(shí)候可以忽略低次項(xiàng))
