據(jù)說全棧路線圖是這樣的辙芍，詳細地連 DevOps 都不得不被掩蓋住一截。
[圖片上傳失敗...(image-930165-1509644610359)]](http://upload-images.jianshu.io/upload_images/2558748-d3e0d4da018a1d3a.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
全棧工程師，F(xiàn)ull Stack Developer，常是一個較為敏感的話題琉兜，一如深度還是廣度好凯正，一如精讀還是粗讀好一樣。你可以說豌蟋，接下來步入的整個項目是一個實為 Node.JS 的偽全棧項目廊散，但作為有志青年來講，“全椢嗥＃”足以時刻提醒自己是面向軟件工程專業(yè)和互聯(lián)網(wǎng)行業(yè)學習奸汇，找的是不去慣性局限自己視野的一股勁。畢竟：
「任何一個 Facebook 的問題往声，都不是別人的問題」
這次擂找，利用 ThoughtWorks 校企實驗室的團隊項目機會，帶來一個 React.js + Node.js 技術棧的全棧實戰(zhàn)項目：基于番茄工作法的番茄時鐘：“番茄post”浩销。該項目將作為自己和團隊的練手項目贯涎，并及時更新進度。同時慢洋，這一路走下去塘雳，也將是一場軟件工程的項目實戰(zhàn)，對理解軟件開發(fā)流程模型很有幫助普筹。
有了小產(chǎn)品理想，畫大餅很簡單太防，但要能夠搭建一個足以依靠敏捷開發(fā)穩(wěn)步推進的軟件開發(fā)流程妻顶，以大學生的能力還不足以直接上手。這次蜒车，多虧了 ThoughtWorks IT 咨詢師讳嘱，同任我們實驗室老師的 @TW李鵬 老師對功能分析的指導，讓我們理解了項目前期對功能分析和設立多個目標里程碑的重要性并能予落實酿愧。引用老師的話來說沥潭，拆分項目里程碑，有如下優(yōu)缺點嬉挡。
這樣帶來的好處是：
* 我們每個里程碑所需要考慮的問題變小钝鸽，易于分析、思考和掌控
* 每個里程碑要學習的東西比較集中庞钢，不會迷失
* 每個里程碑結束拔恰，有一個完整可用的產(chǎn)品，能夠產(chǎn)生價值焊夸，也能夠給自己帶來成就感
* 如果在假期中時間或者精力不夠了仁连，可以放棄后面的里程碑，至少可以做出功能較少但是可用的東西出來阱穗，而不是一個很大但是沒法使用的半成品
帶來的問題是：
* 為了保證每個里程碑功能的完整饭冬，有時候需要在過程中添加一些額外的功能，而這些功能在最后可能會被丟棄揪阶，有額外的工作量
* 新的里程碑的功能可能會在之前的功能上修改昌抠，如何保證之前的功能不被破壞，需要一定的技巧
隨著我們接下來對“番茄post”全棧項目的推進和文章總結鲁僚，這將是一場程序員的技術戰(zhàn)炊苫，也將是一場工程師的身心戰(zhàn)，智慧與勇毅將帶來最終的成果冰沙。
程序功能分析
“番茄post” 基于番茄工作法侨艾，旨在向用戶提供個性化、社區(qū)化的時間管理環(huán)境拓挥，提高工作效率唠梨，改善生活品質，經(jīng)過功能拆解歷程侥啤，它的前期版本將具有以下功能：
- 發(fā)布番茄：每發(fā)布一個番茄当叭，記錄剛剛發(fā)布的一個番茄工作內(nèi)容。
- 展示番茄：將發(fā)布的所有番茄內(nèi)容能夠展示出來盖灸。
- 登錄/注冊：可以向多個用戶提供服務蚁鳖。
- 關注他人：增加用戶多維鏈接，促進雙向激勵赁炎。
- 評論番茄：促進用戶交流醉箕、鼓勵。
- 番茄排行：展示熱門番茄徙垫，讓用戶有所榜樣琅攘。
功能拆解歷程
根據(jù)“有社區(qū)的番茄工作法軟件”為目標同時列出的有添加番茄、暫停番茄等與前端視覺效果有關的功能并以為然作為重點松邪，經(jīng)過老師帶領我們對產(chǎn)品需求進行的細細挖掘下發(fā)現(xiàn)坞琴，“番茄post”需要解決的核心需求點在于：
- 改善用戶拖延癥、焦慮癥逗抑、提高用戶工作效率
- 解決能夠隨時看到他人近期完成的基于番茄工作法的內(nèi)容來激勵自己
- 滿足用戶間對于時間管理剧辐、個人成長等平臺話題的社交渴求
- 能和任意平臺用戶一起指定多日番茄計劃互相監(jiān)督互相激勵
以上大部分強調(diào)的是，“番茄post”更偏向社交化時間管理邮府，前期應削弱對番茄的前端功能效果實現(xiàn)而重在搭建能夠發(fā)布番茄荧关、社交激勵的社區(qū)平臺。
以下里程碑結合功能復雜度和技術難點進行前期劃分褂傀。
第一個里程碑：搭架子
平臺開發(fā)環(huán)境第一性忍啤，提前了解將要使用的技術將決定架子的內(nèi)在。考慮到平臺多樣性和團隊精力的有限性同波，以下列出的開發(fā)環(huán)境將作為第一版出現(xiàn)鳄梅。
- 用戶平臺：Web 瀏覽器
- 編程語言：JavaScript
- 前端框架：React.js
- 運行環(huán)境：Node.js
- 構建工具：NPM
最終，只需要能夠運行出一個簡單的 Hello World 頁面即可未檩。
驗收條件
- 其他人可以方便的獲取你的代碼(Github)戴尸。
- 其他人可以通過你的說明文件，在本地將服務器快速的運行起來冤狡，看到頁面(README.md)孙蒙。
- 通過簡單的頁面可以證明你使用的技術棧和主要的庫等已經(jīng)配置正確；
- 代碼以“小步”方式提交到github上悲雳，并且每個commit都有清楚的描述挎峦；
- 若干篇博客用來記錄你的學習收獲和疑問。
第二個里程碑：數(shù)據(jù)庫搭建和番茄的發(fā)布及其頁面
最基本的功能是對番茄的“增刪改查”合瓢，在這個里程碑中坦胶，我們先實現(xiàn)對番茄的發(fā)布，即增加到數(shù)據(jù)庫中歪玲。制作番茄發(fā)布頁面迁央。
驗收條件
- 任何人可以在賬號密碼正確的情況下訪問數(shù)據(jù)庫；
- 數(shù)據(jù)庫中的相關番茄表單結構確立并能夠看到滥崩；
- 任何人都可以看到番茄發(fā)布頁面里有一個輸入框和發(fā)布番茄按鈕岖圈；
- 任何人都可以通過輸入框填補番茄內(nèi)容并點擊發(fā)布按鈕發(fā)布一個番茄；
- 點擊發(fā)布番茄按鈕后的相關錯誤提示信息能夠得到展示钙皮；
- 發(fā)布番茄后蜂科，數(shù)據(jù)庫里要能夠看到該番茄及其內(nèi)容和發(fā)布時間；
- 代碼以“小步”方式提交到github上短条，并且每個commit都有清楚的描述导匣；
- 若干篇博客用來記錄你的學習收獲和疑問。
第三個里程碑：番茄的展示與刪除及其頁面
這一步茸时，在我們將番茄及其相關信息更新到數(shù)據(jù)庫后贡定，要能夠將數(shù)據(jù)讀取出來并在前臺展示，提供刪除按鈕并能刪除成功可都。番茄的展示與刪除的頁面和番茄發(fā)布頁面同為一個頁面之下缓待，名為用戶個人主頁頁面。
驗收條件
- 任何人都可以看到所有已經(jīng)發(fā)布了的番茄渠牲；
- 任何人都可以刪除所有已經(jīng)發(fā)布了的番茄旋炒；
- 刪除番茄后，該番茄將從數(shù)據(jù)庫中刪除并不會再展示到前臺签杈；
- 代碼以“小步”方式提交到github上瘫镇，并且每個commit都有清楚的描述；
- 若干篇博客用來記錄你的學習收獲和疑問。
第四個里程碑：登錄/注冊功能及相關頁面
之前的里程碑都在于搭建針對單獨用戶的核心功能铣除，這一步來搭建用戶平臺谚咬。
驗收條件
- 任何人都可以訪問登錄、注冊頁面通孽；
- 任何人都可以注冊一個沒有被注冊的賬號序宦；
- 任何人在某賬號和密碼匹配的情況下都可以登錄該賬號睁壁；
- 登錄背苦、注冊過程中的相關錯誤信息能夠得到展示；
- 登錄成功后潘明，可以訪問自己的番茄發(fā)布與展示頁面行剂；
- 代碼以“小步”方式提交到github上，并且每個commit都有清楚的描述钳降；
- 若干篇博客用來記錄你的學習收獲和疑問厚宰。
第五個里程碑：番茄首頁
這時，每一位用戶都有自己的個人主頁頁面并能通過發(fā)布遂填、刪除番茄來更新自己的時間管理記錄铲觉。番茄首頁將著手打造番茄社交環(huán)境，用來展示所有已注冊過的用戶吓坚，提供社交鏈接撵幽。
驗收條件
- 任何人都可以訪問番茄主頁；
- 任何人都能看到番茄主頁下展示的所有已注冊過番茄平臺的用戶礁击；
- 任何人都能看到番茄主頁下提示的登錄盐杂、注冊按鈕并可以點擊；
- 代碼以“小步”方式提交到github上哆窿，并且每個commit都有清楚的描述链烈；
- 若干篇博客用來記錄你的學習收獲和疑問。
第六個里程碑：關注他人與被他人關注
這一步：關注他人挚躯。
驗收條件
- 任何人都可以訪問某位用戶的個人主頁强衡；
- 任何人都可以看到某位用戶的個人主頁的他關注的人和關注他的人；
- 任何人都可以看到某位用戶的個人主頁下有關注該用戶按鈕码荔；
- 任何人在點擊關注該用戶按鈕后判斷是否登錄漩勤；
- 任何人在關注、登錄過程中的相關錯誤信息能夠得以展示目胡；
- 任何人在成功關注某位用戶后可以在該用戶個人主頁的關注他的人下看到自己锯七；
- 任何人在成功關注某位用戶后可以在自己的個人主頁的我關注的人下看到該用戶；
- 任何人在成功關注某位用戶后再次訪問該用戶主頁時誉己，關注按鈕變成已經(jīng)關注的提示眉尸。
- 代碼以“小步”方式提交到github上，并且每個commit都有清楚的描述；
- 若干篇博客用來記錄你的學習收獲和疑問噪猾。
第七個里程碑：番茄評論
驗收條件
- 任何人可以看到每個已經(jīng)發(fā)布的番茄旁有評論框和評論按鈕霉祸；
- 任何人在沒有登錄情況下可以看到評論框和按鈕無法編輯和點擊并有登錄提示；
- 任何人在登錄的情況下可以評論某個番茄袱蜡；
- 評論成功后能看到該番茄下的最新評論丝蹭；
- 每個番茄下的評論按最新時間由上到下排列；
- 代碼以“小步”方式提交到github上坪蚁，并且每個commit都有清楚的描述奔穿；
- 若干篇博客用來記錄你的學習收獲和疑問。
第八個里程碑：番茄網(wǎng)站上線
正式上線至某 IP 地址或某域名下敏晤。
驗收條件
- 將數(shù)據(jù)庫部署至線上贱田；
- 番茄平臺所有功能在線上調(diào)試成功；
- 任何人能夠通過互聯(lián)網(wǎng)訪問番茄首頁并進行深入操作嘴脾；
- 代碼以“小步”方式提交到github上男摧，并且每個commit都有清楚的描述；
- 若干篇博客用來記錄你的學習收獲和疑問译打。
更多內(nèi)容耗拓，盡請期待
“番茄post”的里程碑寫到這里，可以看到奏司，還有很多細節(jié)沒有深入討論乔询。在敏捷的軟件開發(fā)流程下，鑒于我們開發(fā)者也一直在梳理需求且需求會隨時回爐重塑结澄，先開發(fā)出一個可用可見的真實產(chǎn)品出來再看進一步發(fā)展哥谷。
軟件生存期模型是跨越整個生存期的系統(tǒng)開發(fā)、運作和維護所實施的全部過程麻献、活動和任務的結構框架们妥，其中就包括增量模型這一軟件開發(fā)模型，很符合這一次任務的開發(fā)流程勉吻，圖例如下监婶。
更多內(nèi)容，持續(xù)更新中~齿桃。
- Hello惑惶，我是韓亦樂，現(xiàn)任本科軟工男一枚短纵。軟件工程專業(yè)的一路學習中带污，我有很多感悟，也享受持續(xù)分享的過程香到。如果想了解更多或能及時收到我的最新文章鱼冀，歡迎訂閱我的個人微信號：韓亦樂报破。我的簡書個人主頁中，有我的訂閱號二維碼和 Github 主頁地址千绪；我的知乎主頁 中也會堅持產(chǎn)出充易，歡迎關注。
- 本文內(nèi)部編號經(jīng)由我的 Github 相關倉庫統(tǒng)一管理荸型；本文可能發(fā)布在多個平臺但僅在上述倉庫中長期維護盹靴；本文同時采用【知識共享署名-非商業(yè)性使用-禁止演繹 4.0 國際許可協(xié)議】進行許可。
最早擁有排序概念的機器出現(xiàn)在 1901 至 1904 年間由 Hollerith 發(fā)明出使用基數(shù)排序法的分類機瑞妇，此機器系統(tǒng)包括打孔稿静，制表等功能，1908 年分類機第一次應用于人口普查踪宠，并且在兩年內(nèi)完成了所有的普查數(shù)據(jù)和歸檔自赔。
Hollerith 在 1896 年創(chuàng)立的分類機公司的前身妈嘹，為電腦制表記錄公司（CTR）柳琢。他在電腦制表記錄公司（CTR）曾擔任顧問工程師，直到1921年退休润脸，而電腦制表記錄公司（CTR）在1924年正式改名為IBM柬脸。
---- 摘自《維基百科 - 插入排序》
期中已到，期末將至毙驯〉苟椋《算法設計與分析》的“預習”階段藉此開始~。在眾多的算法思想中爆价，如果你沒有扎實的數(shù)據(jù)結構的功底垦巴，不知道棧與隊列，哈希表與二叉樹铭段，不妨可以從排序算法開始練手骤宣。縱觀各類排序算法序愚，常見的憔披、經(jīng)典的排序算法將由此篇引出。
排序算法的輸出必須遵守的下列兩個原則：
- 輸出結果為遞增序列（遞增是針對所需的排序順序而言）
- 輸出結果是原輸入的一種排列爸吮、或是重組
十大經(jīng)典的排序算法及其時間復雜度和穩(wěn)定性如上表所示芬膝。判斷一個排序算法是否穩(wěn)定是看在相等的兩個數(shù)據(jù)排序算法執(zhí)行完成后是否會前后關系顛倒，如若顛倒形娇，則稱該排序算法為不穩(wěn)定锰霜，例如選擇排序和快速排序。
排序前：(4, 1) (3, 1) (3, 7)（5, 6）
排序后：(3, 1) (3, 7) (4, 1) (5, 6) （穩(wěn)定桐早，維持次序）
排序后：(3, 7) (3, 1) (4, 1) (5, 6) （不穩(wěn)定癣缅，次序被改變）
00.交換兩個整數(shù)的值
接下來十個經(jīng)典排序算法的詳細探討缺少不了交換兩個整數(shù)值的掌握纫事，這里回顧一下其中三種方交換法：用臨時變量交換兩個整數(shù)的值(SwapTwo_1)、不用第三方變量交換兩個整數(shù)的值(SwapTwo_2)所灸、使用位運算交換兩個整數(shù)的值(SwapTwo_3)丽惶。其中用臨時變量交換兩個整數(shù)的值效率最高，后倆者只適用于內(nèi)置整型數(shù)據(jù)類型的交換爬立，并不高效钾唬。
void SwapTwo_1 (int *a, int* b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void SwapTwo_2 (int *a, int *b) {
*a = *a + *b;
*b = *a - *b;
*a = *a - *b;
}
void SwapTwo_3 (int *a, int *b) {
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
01. 冒泡排序(BubbleSort)
先不說公司面試筆試，大學實驗室的納新題里最常有的就是冒泡排序侠驯。冒泡排序重復地走訪過要排序的數(shù)列抡秆，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來吟策。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端儒士。由于它的簡潔，冒泡排序通常被用來對于程序設計入門的學生介紹算法的概念檩坚。
[圖片上傳失敗...(image-6edc3d-1509644592135)]](http://upload-images.jianshu.io/upload_images/2558748-990f8de3fbdbb50d.gif?imageMogr2/auto-orient/strip)
上圖可見着撩，冒泡排序算法的運作如下：
- 比較相鄰的元素。如果第一個比第二個大匾委，就交換他們兩個拖叙。
- 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對赂乐。這步做完后薯鳍，最后的元素會是最大的數(shù)。
- 針對所有的元素重復以上的步驟挨措，除了最后一個挖滤。
- 持續(xù)每次對越來越少的元素重復上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較浅役。
通俗來講斩松，整個冒泡排序就是通過兩次循環(huán)，外層循環(huán)將此輪最大(小)值固定到此輪尾部担租，內(nèi)層循環(huán)“冒泡”比較相鄰的兩個元素并決定是否交換位置砸民。
從上圖也可理解冒泡排序如何將每一輪最大（小）值固定到此輪尾部：尾部總為有序狀態(tài)奋救，前面無序狀態(tài)區(qū)根據(jù)大小規(guī)則冒泡向后方傳遞最值岭参。
/*
* 冒泡排序。每次外循環(huán)將最值固定到數(shù)組最后
* @param: {int []} arr
* @param: {int} len
* @return null;
*/
void BubbleSort (int arr[], int len) {
int i, j, temp;
for (int i = 0; i < len - 1; i++) {
// 每趟 i 循環(huán)將最大(小)值固定到最后一位
for (int j = 0; j < len - 1 - i; j++) {
// 每趟 j 循環(huán)循環(huán)沒有被固定到后方的數(shù)字
if (arr[j] > arr[j + 1]) {
// arr[j] < arr[j + 1] 代表從小到大排序
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
更多十大經(jīng)典排序算法請戳我的 Github 倉庫 @LeetCode-C
02. 選擇排序(SelectionSort)
選擇排序首先在未排序序列中找到最谐⑺摇（大）元素演侯，存放到排序序列的起始位置，然后背亥，再從剩余未排序元素中繼續(xù)尋找最忻爰省（大）元素悬赏，然后放到已排序序列的末尾。以此類推娄徊，直到所有元素均排序完畢闽颇。
選擇排序的主要優(yōu)點與數(shù)據(jù)移動有關。如果某個元素位于正確的最終位置上寄锐，則它不會被移動兵多。選擇排序每次交換一對元素，它們當中至少有一個將被移到其最終位置上橄仆，因此對n個元素的表進行排序總共進行至多n-1次交換剩膘。在所有的完全依靠交換去移動元素的排序方法中，選擇排序屬于非常好的一種盆顾。
上圖左下角和右上角可以分別看做排序序列起始位置(已排序區(qū))和排序序列末尾(未排序區(qū))怠褐，左下角一直穩(wěn)定更新，但選擇排序不穩(wěn)定您宪，即排序后曾經(jīng)相同的兩個元素的前后位置關系可能會發(fā)生顛倒奈懒。
/*
* 選擇排序。每次外循環(huán)選擇最值固定到數(shù)組開始
* @param: {int []} arr[]
* @param: {int} len
* @return null;
*/
void SelectionSort (int arr[], int len) {
int i, j, temp, min;
for (i = 0; i < len - 1; i++) {
min = i;
for (j = i + 1; j < len - 1; j++) {
if (arr[min] > arr[j]) {
// 只需找到最小的值的位置后一次性替換
min = j;
}
temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
}
更多十大經(jīng)典排序算法請戳我的 Github 倉庫 @LeetCode-C
03. 插入排序(InsertionSort)
插入排序的工作原理是通過構建有序序列蚕涤，對于未排序數(shù)據(jù)筐赔，在已排序序列中從后向前掃描，找到相應位置并插入揖铜。插入排序在實現(xiàn)上，通常采用 in-place
排序（即只需用到O(1)的額外空間的排序）达皿，因而在從后向前掃描過程中天吓，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間峦椰。
一般來說龄寞，插入排序都采用 in-place 在數(shù)組上實現(xiàn)。具體算法描述如下：
- 從第一個元素開始汤功，該元素可以認為已經(jīng)被排序
- 取出下一個元素物邑，在已經(jīng)排序的元素序列中從后向前掃描
- 如果該元素（已排序）大于新元素，將該元素移到下一位置
- 重復步驟 3滔金，直到找到已排序的元素小于或者等于新元素的位置
- 將新元素插入到該位置后
- 重復步驟 2~5
如果比較操作的代價比交換操作大的話色解，可以采用二分查找法來減少比較操作的數(shù)目部宿。該算法可以認為是插入排序的一個變種惊科，稱為二分查找插入排序。這里先不做涉及算灸。
/*
* 插入排序忿族。前面有序的數(shù)字循環(huán)向后留給滿足條件的第一個無序數(shù)字
* @param: {int []} arr
* @param: {int} len
* @return null;
*/
void InsertionSort (int arr[], int len)
{
int i, j, temp;
for (i = 1; i < len; i++) {
// 與已排序的數(shù)逐一比較锣笨，大于 temp 時蝌矛，該數(shù)向后移
temp = arr[i];
// 如果將賦值放到下面的for循環(huán)內(nèi), 會導致在第10行出現(xiàn) j 未聲明的錯誤
j = i - 1;
for (; j >= 0 && arr[j] > temp; j--) {
// j 循環(huán)到-1時，由于短路求值错英，不會運算 arr[-1]
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
// 被排序數(shù)放到正確的位置
}
}
更多十大經(jīng)典排序算法請戳我的 Github 倉庫 @LeetCode-C
04. 希爾排序(ShellSort)
希爾排序按其設計者希爾（Donald Shell）的名字命名入撒，該算法由1959年公布。希爾排序也稱遞減增量排序算法椭岩，是插入排序的一種更高效的改進版本衅金。希爾排序是非穩(wěn)定排序算法。希爾排序是基于插入排序的以下兩點性質而提出改進方法的：
- 插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時簿煌，效率高氮唯，即可以達到線性排序的效率
- 插入排序一般來說是低效的，因為插入排序每次只能將數(shù)據(jù)移動一位
希爾排序通過將比較的全部元素分為幾個區(qū)域來提升插入排序的性能姨伟。這樣可以讓一個元素可以一次性地朝最終位置前進一大步惩琉。然后算法再取越來越小的步長進行排序，算法的最后一步就是普通的插入排序夺荒，但是到了這步瞒渠，需排序的數(shù)據(jù)幾乎是已排好的了（此時插入排序較快）。
步長的選擇是希爾排序的重要部分伍玖。只要最終步長為1任何步長序列都可以工作。算法最開始以一定的步長進行排序剿吻。然后會繼續(xù)以一定步長進行排序窍箍，最終算法以步長為1進行排序。當步長為1時丽旅，算法變?yōu)椴迦肱判蛞@就保證了數(shù)據(jù)一定會被排序。
已知的最好步長序列是由 Sedgewick 提出的(1, 5, 19, 41, 109,...)榄笙，這項研究也表明“比較在希爾排序中是最主要的操作邪狞，而不是交換∶┳玻”用這樣步長序列的希爾排序比插入排序要快帆卓，甚至在小數(shù)組中比快速排序和堆排序還快，但是在涉及大量數(shù)據(jù)時希爾排序還是比快速排序慢米丘。
/*
* 希爾排序剑令。
* @param: {int []} arr
* @param: {int} len
* @return null;
*/
void ShellSort(int arr[], int len) {
int gap, i, j;
int temp;
for (gap = len >> 1; gap > 0; gap >>= 1) {
// gap 為間隔，每次間隔折半
for (i = gap; i < len; i++) {
// 循環(huán)該輪數(shù)組后半段
temp = arr[i];
for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
// 根據(jù)當前 grap 間隔和條件進行插入排序前的后移
arr[j + gap] = arr[j];
}
// 插入到當前位置
arr[j + gap] = temp;
}
}
}
更多十大經(jīng)典排序算法請戳我的 Github 倉庫 @LeetCode-C
05. 歸并排序(MergeSort)
歸并排序是創(chuàng)建在歸并操作上的一種有效的排序算法蠕蚜，效率為 O(n log n)尚洽。1945年由約翰·馮·諾伊曼首次提出。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用靶累，且各層分治遞歸可以同時進行腺毫。
歸并操作（merge）癣疟，也叫歸并算法，指的是將兩個已經(jīng)排序的序列合并成一個序列的操作潮酒。歸并排序算法依賴歸并操作睛挚。
歸并排序用迭代法和遞歸法都可以實現(xiàn)，迭代法的算法步驟為：
- 申請空間急黎，使其大小為兩個已經(jīng)排序序列之和扎狱，該空間用來存放合并后的序列
- 設定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置
- 比較兩個指針所指向的元素勃教，選擇相對小的元素放入到合并空間淤击，并移動指針到下一位置
- 重復步驟3直到某一指針到達序列尾
- 將另一序列剩下的所有元素直接復制到合并序列尾
遞歸法的算法步驟為：
- 將序列每相鄰兩個數(shù)字進行歸并操作，形成 floor(n/2) 個序列故源，排序后每個序列包含兩個元素
- 將上述序列再次歸并污抬，形成 floor(n/4) 個序列，每個序列包含四個元素
- 重復步驟 2绳军，直到所有元素排序完畢
/*
* 歸并排序印机。迭代版
* @param: {int []} arr
* @param: {int} len
* @return null;
*/
void MergeSort_1 (int arr[], int len) {
int* a = arr;
int* b = (int*) malloc(len * sizeof(int));
int seg, start;
for (seg = 1; seg < len; seg += seg) {
for (start = 0; start < len; start += seg + seg) {
int low = start, mid = Min (start + seg, len), high = Min(start + seg + seg, len);
int k = low;
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
while (start1 < end1 && start2 < end2)
b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
while (start1 < end1)
b[k++] = a[start1++];
while (start2 < end2)
b[k++] = a[start2++];
}
int* temp = a;
a = b;
b = temp;
}
if (a != arr) {
int i;
for (i = 0; i < len; i++)
b[i] = a[i];
b = a;
}
free(b);
}
int Min(int x, int y) {
return x < y ? x : y;
}
/*
* 歸并排序。遞歸版
* @param: {int []} arr
* @param: {const int} len
* @return null;
*/
void MergeSort_2 (int arr[], const int len) {
int reg[len];
merge_sort_recursive(arr, reg, 0, len - 1);
}
void merge_sort_recursive (int arr[], int reg[], int start, int end) {
if (start >= end)
return;
int len = end - start, mid = (len >> 1) + start;
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
merge_sort_recursive(arr, reg, start1, end1);
merge_sort_recursive(arr, reg, start2, end2);
int k = start;
while (start1 <= end1 && start2 <= end2)
reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
while (start1 <= end1)
reg[k++] = arr[start1++];
while (start2 <= end2)
reg[k++] = arr[start2++];
for (k = start; k <= end; k++)
arr[k] = reg[k];
}
總結【上】
這篇文章“十大經(jīng)典排序算法及其 C 語言實現(xiàn)【上】”引出了十大經(jīng)典算法的前五個并用 C 語言實踐：冒泡排序门驾、選擇排序射赛、插入排序、希爾排序和歸并排序奶是，并作出了充足的圖文解釋楣责。即將推出的“十大經(jīng)典排序算法及其 C 語言實現(xiàn)【下】”將對剩下五個經(jīng)典算法快速排序、堆排序诫隅、計數(shù)排序腐魂、桶排序、基數(shù)排序作出完善逐纬，盡請期待~。
- Hello削樊，我是韓亦樂豁生，現(xiàn)任本科軟工男一枚。軟件工程專業(yè)的一路學習中漫贞，我有很多感悟甸箱，也享受持續(xù)分享的過程。如果想了解更多或能及時收到我的最新文章迅脐，歡迎訂閱我的個人微信號：韓亦樂芍殖。我的簡書個人主頁中，有我的訂閱號二維碼和 Github 主頁地址谴蔑；我的知乎主頁 中也會堅持產(chǎn)出豌骏，歡迎關注龟梦。
- 本文內(nèi)部編號經(jīng)由我的 Github 相關倉庫統(tǒng)一管理；本文可能發(fā)布在多個平臺但僅在上述倉庫中長期維護窃躲；本文同時采用【知識共享署名-非商業(yè)性使用-禁止演繹 4.0 國際許可協(xié)議】進行許可计贰。
