歸并排序的特點是:?先拆分, 再排序。
而使用柱狀遞歸樹圖可以讓你非常清晰地感受到歸并排序的這個特點。
1 柱狀遞歸樹圖
什么是柱狀遞歸樹圖呢??
柱狀遞歸樹圖?就是?柱狀圖+樹圖 組合而成
先上一張歸并排序的效果圖快速預覽下
柱狀圖可以很好地把數(shù)字的大小排列體現(xiàn)出來。
樹圖就可以把每次遞歸之后, 數(shù)字的大小排列變化很好地體現(xiàn)出來。
遞歸的本質就是樹！
這張圖中每一個柱狀圖都表示一次遞歸后的結果,?我們可以非常直觀地看到遞歸的模樣!
希望看完本文后, 再提起歸并排序時, 首先出現(xiàn)在你腦海里的,會是一個柱狀遞歸樹的動畫 : )
下面先說歸并排序的遞歸實現(xiàn)方式:?先遞歸二分, 再排序合并蹂随。
2 遞歸實現(xiàn)
照例我們先對一個長度為16的亂序數(shù)組進行歸并排序
let data = [13,11,7,4,9,8,15,6,5,3,14,2,10,1,16,12]
使用遞歸的實現(xiàn)方式，我們先對數(shù)組進行二分因惭。
把數(shù)組中16個元素先分出8個來, 再從8個中分出4個岳锁，一直遞歸地對左邊的數(shù)組二分下去：
直到還剩下1個數(shù)字時, 遞歸終止，也就是下圖這種情況蹦魔。
終止遞歸后, 回到上一層, 開始對右半部分的數(shù)組進行二分操作激率。
直到右邊的數(shù)組也剩下1個數(shù)字時, 遞歸終止，也就是下圖這種情況勿决。
如果我們對整個數(shù)組遞歸地執(zhí)行二分操作乒躺，執(zhí)行結束之后，?就是下圖的效果：
說多無益, 直接看動圖:
從動畫可以反推出代碼應該是下面這樣的:
理解了遞歸二分低缩，接下來講講歸并排序的第二步嘉冒，排序合并曹货。
3 排序合并
歸并排序是怎么把兩個小的數(shù)組合并回大的數(shù)組呢？
排序合并 顧名思義就是先排序 后合并讳推。
這一步也是歸并排序的重頭戲顶籽，實現(xiàn)歸并排序時我們也會花更多的精力在這一步。
我們先來看看最簡單的情況：兩個長度一的數(shù)組怎么合并為一個有序數(shù)組银觅。
看下圖紅色部分, 我們先對左邊的數(shù)組和右邊的數(shù)組進行比較:
比較小的元素先移到上層數(shù)組中：
最后完成排序合并礼饱，可以看到新合并的數(shù)組是一個有序數(shù)組：
接下來看看復雜點的情況，兩個長度為4的數(shù)組合并為一個數(shù)組：
通過下面這個簡單的動畫演示究驴，我們可以一窺究竟镊绪。
詳細的代碼實現(xiàn)我們在下次更新再進行講解。這里先大概說下邏輯纳胧，我們可以把左右兩個數(shù)組想象成左右兩個指針镰吆。兩個指針一開始都是指向數(shù)組的初始位置0帘撰，然后兩個指針所指向的元素開始比較大小跑慕，較小的那個數(shù)會移到上層數(shù)組中，并且該數(shù)字所在的指針向右移動一格摧找，依次類推核行。
現(xiàn)在我們在上面的遞歸函數(shù)里加入排序合并這步操作。
于是就變成了下面這樣蹬耘，是不是和你想象中的一樣呢芝雪？這里只放左半部分的動畫。
遞歸二分 + 排序合并综苔，這就是歸并排序算法完整的遞歸實現(xiàn)惩系。
最終排序效果圖：
4 非遞歸實現(xiàn)
歸并排序還可以使用非遞歸的方式實現(xiàn)，也就是自底向上如筛，先遍歷拆分, 再排序合并堡牡。
非遞歸的實現(xiàn)方式，采用自底向上的思路杨刨。
對數(shù)組進行
1個一組進行拆分-排序合并;
2個一組進行拆分-排序合并;
4個一組進行拆分-排序合并;
8個一組的方式進行拆分......
這些我們都會在下次更新的文章中配合動畫進行詳細講解晤柄。
最終的排序結果：
5 后續(xù)
下一篇更新將會重點講解歸并排序的實現(xiàn)代碼。
相信大家都可以看到妖胀，?歸并排序的實現(xiàn)重心是第二步“排序合并”芥颈，下一章也會通過動畫對這個過程進行詳細解析。
最后赚抡，目前的樹圖還是有一些缺陷的爬坑，比如樹的節(jié)點之間缺少了線，比如非遞歸實現(xiàn)的一些布局問題等等涂臣，這些問題都會在后續(xù)慢慢完善：）
溫馨提示
本文的動畫使用的是d3.js?和?anim.js妇垢，如果對本文的動畫代碼感興趣，可以關注公眾號"字節(jié)武裝"。
