本文從冒泡排序撩起，對(duì)選擇、插入、希爾、歸并、快排6種經(jīng)典的數(shù)組排序進(jìn)行了深入分析，并詳解其間的關(guān)聯(lián)，讓你深刻理解其中的關(guān)鍵點(diǎn)；同時(shí)對(duì)經(jīng)典的數(shù)據(jù)結(jié)構(gòu)Vector、Stack、Queue、樹(shù)、Map、Set做了歸納總結(jié)，對(duì)其底層的實(shí)現(xiàn)做了解析，分享給大家，作為每一個(gè)中高級(jí)程序員應(yīng)該懂得的算法與排序，祝大家早上走上自己的“成金之路”。
目錄：
1.排序算法
2.數(shù)據(jù)結(jié)構(gòu)
3.資料參考
1.排序算法：
a.起源：
計(jì)算機(jī)從誕生起，就在模擬人這種智能生物的行為，而排序也來(lái)自于日常生活中，最經(jīng)典的冒泡排序即來(lái)源于水泡從水底升上水面，離水面越近，水泡體積越大——由此誕生的冒泡排序思想即為：依次遍歷每個(gè)元素，如果前一個(gè)比后一個(gè)大，則交換兩者的位置。
其缺點(diǎn)有二：第一點(diǎn)每次比較都會(huì)產(chǎn)生交換元素的行為，效率低；第二點(diǎn)，算法復(fù)雜度為O(n^2)
b.針對(duì)缺點(diǎn)一的優(yōu)化：
選擇排序：即每次遍歷只記錄最大元素的下標(biāo)，最后進(jìn)行元素交換；
插入排序：當(dāng)輸入有序程度較高時(shí)，通過(guò)構(gòu)建有序數(shù)組，并將新元素插入到有序數(shù)組中，完成整體的排序，降低元素交互的次數(shù)，缺點(diǎn)是不穩(wěn)定；
希爾排序：插入排序穩(wěn)定穩(wěn)定程度太低，因此通過(guò)主動(dòng)構(gòu)建有序?qū)?間隔n、n/2、n/4...1的有序?qū)?，來(lái)提升“插入排序”的穩(wěn)定性，是插入排序的一種改進(jìn)。
c.針對(duì)缺點(diǎn)二的優(yōu)化：
歸并排序：采用“分治算法思想”，將輸入一分為二，分別排序，通過(guò)“并行”思想來(lái)提升算法效率，復(fù)雜度為O(nlgn)，但是需要額外的arr[n]空間，來(lái)進(jìn)行合并；
快速排序：對(duì)歸并排序的改進(jìn)，在不需要額外空間的情況下，對(duì)數(shù)組遍歷，按對(duì)選定元素的比較進(jìn)行劃分，小的集中在左邊，大的集中在右邊；分別對(duì)兩邊進(jìn)行排序——整體的思路與構(gòu)建二叉樹(shù)一致，其復(fù)雜度為O(nlgn)。
d.偽代碼總結(jié)如下：
2.數(shù)據(jù)結(jié)構(gòu)：
教學(xué)視頻參考斯坦福公開(kāi)課《抽象編程》，地址為http://open.163.com/special/opencourse/abstractions.html
這里對(duì)主要的數(shù)據(jù)結(jié)構(gòu)進(jìn)行了拆解，如下圖
上圖只是詳解了其底層的結(jié)構(gòu)，但是涉及到使用時(shí)，還需要提供一些常見(jiàn)接口，供調(diào)用者使用，如size()、iterator()/hasnext()/next()x、add()/remove()、contain()、isEmpty()等；見(jiàn)代碼實(shí)現(xiàn)分享鏈接：http://pan.baidu.com/s/1hsoReNa 密碼：h9q0。
另，附上《抽象編程》總結(jié)筆記，鏈接：http://pan.b
延伸閱讀
學(xué)習(xí)是年輕人改變自己的最好方式