亂序.PNG

上面的同學請保持秩序宛篇。娃磺。。本章叫倍，來研究一下排序算法偷卧。
排序算法在大部分情況下并不具備直接商業(yè)應用的條件，但是對我們理解排序的本質思想是非常有幫助的吆倦，正所謂萬變不離其宗听诸。所以關于排序算法，我也更多的是先從舉一反三的思考問題的角度去復習蚕泽。

排序算法大全

排序算法.PNG

排序算法的評估要素

1.穩(wěn)定性：穩(wěn)定性與實現(xiàn)方式有很強的相關性晌梨，但是如果是按相對最優(yōu)（教科書）的算法步驟實現(xiàn)，每種算法的穩(wěn)定性是固定的须妻。
2.時間復雜度：與算法的數(shù)學思想強相關仔蝌。例如二分的思想，遞歸的思想荒吏，遍歷的思想
3.空間復雜度：內存與資源的開銷敛惊，可以針對不同場景提供不同的算法

插入類

直接插入排序

算法思想

每一次遍歷，將一個待排序關鍵字（只要是沒有被處理的關鍵字即可）按照其值的大小插入到已經(jīng)排好的部分有序序列中绰更，插入方式取決于排序方式（從小到大豆混，則按照從小到大方式插入到有序序列中）篓像，直到所有關鍵字都被插入到有序序列為。
該算法的核心思想：“大事化小皿伺，以0為起始”员辩。
該算法比較簡單，就不提供圖示樣例了鸵鸥，腦補一下奠滑。

時間復雜度

該算法存在兩個步驟：
1--遍歷全部關鍵字，這個是必不可少的
2--插入操作妒穴，所以需要對已排序序列做移動宋税，移動次數(shù)與原序列的“有序度（原序列與目標序列的初始匹配度）”有關
所以算法復雜度，平均是n（step1）*n（step2）讼油，即O(n2)杰赛；最壞的情況下，step2每次要移動全部已排序序列矮台，所以會導致最壞復雜度為也是O(n2)乏屯；最好的情況下，step2不需要做任何操作瘦赫，新的關鍵字插入有序序列的時候辰晕，不需要對原有序序列做操作，即最好情況為O(n)确虱。

空間復雜度

插入動作過程中我們需要一個temp用來存儲關鍵字含友，所以通常空間復雜度為O(1)校辩。如果崗警說窘问，我搞個temp[n]，然后拷貝有序序列宜咒。南缓。那我想說，也可以荧呐，但是不標準汉形。

穩(wěn)定性

思考一下，排序前后的序列倍阐，對重復的關鍵字是否會有變化呢概疆？一般可以以舉反例的方式來推理。比如有一個序列 3 1 1 5 2 2 9峰搪，按照從小到大排序岔冀。第二個1在插入的時候，如果插入在第一個1之前概耻，那么這個實現(xiàn)就不穩(wěn)定排序使套，但是如果插入在第二個（即最后一個重復關鍵字）之后就算是穩(wěn)定的罐呼。然而，上述反例是偽證侦高。因為我們不可能知道最后一個重復關鍵字在哪嫉柴，如果要遍歷，那就不是O(n2)的復雜度了奉呛。所以通常的合理實現(xiàn)计螺，應當是選擇插入在第一個1前面，所以我認為直接插入排序的實現(xiàn)一定是不穩(wěn)定瞧壮，盡管理論上具備穩(wěn)定的可能性登馒。

折半插入排序

算法思想

這個算法就是對插入排序的一個改良。插入排序在尋找插入位置的時候咆槽，往往是從頭到尾順序遍歷陈轿，這對一個已經(jīng)有序的序列并不是最優(yōu)的遍歷方案，所以將遍歷方案優(yōu)化為二分法遍歷秦忿。即所謂折半插入麦射。

算法復雜度

折半插入排序減少了比較元素的次數(shù)，約為O(nlogn)小渊，比較的次數(shù)取決于表的元素個數(shù)n。因此茫叭，折半插入排序的時間復雜度仍然為O(n2)酬屉，所以當數(shù)據(jù)量有一定規(guī)模的情況下，該算法會表現(xiàn)出遠優(yōu)于直接插入的性能揍愁。

希爾排序

算法思想

希爾排序又叫做縮小量排序呐萨，其本質還是插入排序，特別之處在于將待排序序列按某種規(guī)則分成幾個子序列莽囤，分別對幾個子序列進行直接插入排序谬擦。規(guī)則的關鍵在于增量的選擇，如果增量為1朽缎，就是直接插入排序惨远。說了這么多，來看個實例吧

希爾排序.PNG

時間復雜度

按照希爾的方案選取增量扬蕊，那么對于n序列長度的排序搀别，最壞情況下為O(n的平方)，當n在某個特定范圍時厨相，約為O(n的1.3次方)
關于希爾排序算法復雜度的證明過程比較復雜领曼，待后續(xù)有時間再詳解。

空間復雜度

與插入排序的邏輯一致蛮穿，為O(1)

穩(wěn)定性

由于插入關鍵字的緣故庶骄，希爾排序也是非穩(wěn)定排序。

交換類

冒泡排序

算法思想

此處略去100字践磅。

時間復雜度

因為要做兩個循環(huán)才能完成全部冒泡单刁，所以時間復雜度O(n的平方)

空間復雜度

只需要一個temp即可，O(1)府适；

穩(wěn)定性

冒泡在交換過程中羔飞，如果比較大小相等并不會執(zhí)行交換（性能考慮），所以冒泡是穩(wěn)定的檐春。

快速排序

算法思想

快速排序也是交換類排序逻淌，他通過“多次劃分”實現(xiàn)排序操作。已升序為例疟暖，執(zhí)行流程如下
1）選擇1個當前子序列的關鍵字作為軸卡儒，通常從第一個關鍵字開始
2）將大于關鍵字的放在右邊，小于關鍵字的放在左邊俐巴，經(jīng)過一輪循環(huán)后骨望，中軸關鍵字的左邊為一個序列，右邊為一個序列
3）當遍歷完一輪全部數(shù)據(jù)后欣舵，全部數(shù)據(jù)將會被分為兩組擎鸠，然后本輪循環(huán)結束。假如你沒看過教科書的灌輸思維缘圈，這里應該如何去判定“全部數(shù)據(jù)完成一次遍歷”這個操作呢劣光？
4）分別對左邊序列和右邊序列執(zhí)行1、2糟把、3操作赎线，直到子序列為1個元素為止。

快排.PNG

時間復雜度

交換過程采取了二分法糊饱，所以遍歷次數(shù)為log2n垂寥，由于始終需要對n個元素進行比較，所以平均復雜度為O(nlog2n)，最壞的情況下滞项，二分子序列的情況需要執(zhí)行n次（例如一個完全逆序的數(shù)組進行排序）狭归，則最壞復雜度為O(n的平方)

空間復雜度

直觀來看，快排只用了一個temp文判，所以空間復雜度應該是O(1)过椎，然后快排的實現(xiàn)是遞歸，遞歸是需要椣凡郑空間開銷的疚宇，空間復雜度等于遞歸次數(shù)*O(1)，即O(nlog2n)赏殃。

穩(wěn)定性

快排的本質是交換類排序敷待，交換類排序在等于的情況下是不發(fā)生交換，所以快排也是穩(wěn)定排序仁热。

選擇類

簡單選擇排序

算法思想

我認為這是世界上最直觀最簡單的算法榜揖，連小朋友打撲克都會的算法。
找出最小的放在第一位抗蠢，次小放在第二位举哟，再次放在第三位，依次排序迅矛。妨猩。還有啥比這更簡單的嗎

時間復雜度

直接插入排序就兩步 1）找到最小，需要輪詢 2）放到對應的位置秽褒，需要將已有序列統(tǒng)一向后挪動壶硅，等于插隊，其他人往后站震嫉，依然需要輪詢已有序列森瘪，兩遍輪詢牡属，時間復雜度O(n的平方)票堵；，逮栅，
這里要注意悴势，直接插入排序和直接選擇排序的區(qū)別，雖然都有插入這個動作措伐，但是前者是移動有序序列特纤，后者是挪動無序序列讓出空間。這兩者有直接區(qū)別侥加，所以閱讀代碼的時候艳狐，不要看到insert就想到一定是插入排序了扭倾。

空間復雜度

挪動過程媳叨，并不需要新建數(shù)組魁衙，所以空間復雜度O(1);

穩(wěn)定性

序列在發(fā)生交換的時候，會改變原有相同關鍵字的順序湾盗，所以選擇排序是不穩(wěn)定的。
例如7，8泳唠，7，3宙搬，9笨腥，7和3交換以后，兩個7的相對位置已經(jīng)發(fā)生了變化勇垛。

堆排序

（在這個階段提堆排序會感覺有點跳躍性脖母，直接從一個超級簡單的算法到了一個較為復雜的算法，但是沒辦法窥摄。镶奉。選擇排序只有這兩種）

背景知識補齊

因為我在算法這部分并沒有考慮再去討論數(shù)據(jù)結構了，但是這里這個算法用到了堆崭放，所以再把堆相關的知識拿出來復習一下哨苛。
堆是一種基本數(shù)據(jù)結構，可以將其理解為一個完全二叉樹币砂，而這顆二叉樹滿足：任何一個非葉節(jié)點值都不大于(或不小于)其左右孩子節(jié)點的值建峭。若父親大孩子小，稱為大頂堆决摧；父親小孩子大稱為小頂堆亿蒸。由此可見，如果以大頂堆為例掌桩，根節(jié)點就是該序列最大值边锁。

算法思想

利用堆的特征，將待排序序列構成一個大頂堆波岛，然后移除根節(jié)點茅坛，將剩余節(jié)點再轉化成一個大頂堆，一次完成排序操作则拷。
問題1：如何將無序序列轉化為大頂堆
問題2：將堆頂元素挪走以后贡蓖，如何將剩余元素繼續(xù)做成大頂堆。是重復問題1的解法去遞歸煌茬，還是另有方法斥铺。
如果很想深究上述兩個問題的答案，建議充分復習一下二叉樹和完全二叉樹的數(shù)據(jù)結構坛善。我這里給出上述兩個問題的解法晾蜘。
排序步驟如下：
1）將無序序列轉化成一個完全二叉樹邻眷，如圖

堆.PNG

2）對該完全二叉樹從第一個非葉節(jié)點開始從右至左從下往上堆每個節(jié)點進行調整
調整方法：將該節(jié)點的值域其孩子節(jié)點比較，如果有大于該節(jié)點的孩子節(jié)點剔交，則從中選出最大的一個與該節(jié)點進行交換耗溜。該節(jié)點如果存在多層的孩子，則需要層層往下執(zhí)行上述步驟省容，至到該節(jié)點的所有孩子均小于該節(jié)點抖拴。
3）完成2以后，得到一個大頂堆腥椒。將根節(jié)點與最小的葉子節(jié)點交換（這么做也是為了最小化內存空間占用阿宅，和前面的排序思想一樣。做算法設計笼蛛，必須精益求精洒放，做到極致，算法是小杠桿滨砍，一點點開銷堆整個產(chǎn)業(yè)帶來的可能就是巨大的成本浪費）往湿，這樣將整棵樹分為有序和無序兩部分。對于無序部分惋戏，再次執(zhí)行上述2)步驟领追。直到無序隊列只剩最后一個元素。還是用圖來說明這個過程响逢。

1.PNG

2.PNG

時間復雜度

算法復雜度為O(nlog2n)窑邦，至于怎么來的擅威，我會在算法基礎2.2中實現(xiàn)堆排序的代碼，屆時用代碼來解釋上述圖中復雜的節(jié)點遷移變化的時間開銷冈钦。
這里有一點需要明確郊丛，堆排序如此復雜，為什么還要用它。厉熟〉贾眩可能大家已經(jīng)意識到，堆排序是一個二叉樹遍歷問題揍瑟，二叉樹的遍歷白翻，最好最壞時間復雜度都是O(nlog2n)，而快排的最壞復雜度是O(n的平方)绢片。所以滤馍，當數(shù)據(jù)量很大但是卻只需要找出排名前幾的關鍵字時，堆排序有較為明顯的優(yōu)勢底循。
比如考試成績排名巢株，需要在20W考生里面找到廣東省排名前100的，快排就會比較耗時熙涤，堆排序優(yōu)勢明顯阁苞。

空間復雜度

空間并不隨數(shù)據(jù)量大小的變化而變化，所以空間復雜度為O(1)祠挫。

穩(wěn)定性

在舉個例子說明：8 17(a) 26 17(b)那槽，
如果堆頂8先輸出，17(b)跑到堆頂等舔，然后堆穩(wěn)定倦炒，繼續(xù)輸出堆頂，即17(b)软瞎，于是17(b)出現(xiàn)在了17(a)前面逢唤，不穩(wěn)定。
理論過程描述：
堆的特征是節(jié)點i的孩子為2 * i和2 * i + 1節(jié)點涤浇，大頂堆要求父節(jié)點大于等于其2個子節(jié)點鳖藕。于是，對于一個n 序列只锭，堆排序的過程是從第n / 2開始和其子節(jié)點共3個值選擇最大（大頂堆）著恩，這3個元素之間的選擇不會破壞穩(wěn)定性。但當為n / 2 - 1蜻展， n / 2 - 2喉誊， ... 1這些個父節(jié)點選擇元素時，就會破壞穩(wěn)定性纵顾。有可能第n / 2個父節(jié)點交換把后面一個元素交換過去了伍茄，而第n / 2 - 1個父節(jié)點把后面一個相同的元素沒有交換，那么這2個相同的元素之間的穩(wěn)定性就被破壞了施逾。所以敷矫，堆排序不是穩(wěn)定的排序算法例获。

歸并類

歸并排序

算法思想

歸并排序是一個分治的過程：先將整個序列分為兩半，堆每一辦進行歸并排序曹仗，將得到兩個有序序列榨汤，然后將兩個有序序列合并為一個即可。其實怎茫，歸并算法的關鍵點分裂和合并收壕。
來看個圖

分裂.PNG

合并.PNG

時間復雜度

歸并排序的時間復雜度，用數(shù)學歸納來推導一下轨蛤。
第一趟歸并需要執(zhí)行2(n/2)=n次基本操作（其中2為子序列關鍵字的個數(shù)之和啼器，n/2為要歸并的子序列堆的個數(shù)，每個子序列對執(zhí)行一次merge操作俱萍，也就是兩次(比較+交換)基本操作）
第二趟歸并需要執(zhí)行4(n/4)=n
第三趟歸并需要執(zhí)行8(n/8)=n
第k趟歸并需要執(zhí)行2的k次方(n/2的k次方)=n
……………………
當n/2的k次方 = 1時端壳，即需要歸并的兩個子序列長度均為原序列的一半時，歸并排序結束枪蘑，此時k=log2n损谦，即總共需要log2n趟排序，時間復雜度為O(nlog2n)

空間復雜度

歸并過程中岳颇，我們需要轉儲整個序列照捡，所以空間復雜度為O(n)

穩(wěn)定性

可以想象，兩個項目的元素话侧，在分裂和合并過程中栗精，并不會發(fā)生相對位置的變化。所以歸并排序是穩(wěn)定的瞻鹏。

線性時間比較類

怎么突然冒出一個線性時間呢悲立？其實前面的所有排序都是非線性時間比較類排序。
非線性時間比較排序--基于比較的排序新博，其算法時間復雜度不能突破O（nlogn）薪夕。
線性時間比較排序--不基于比較的排序，其算法時間復雜度可以突破O（nlogn）赫悄。
至于為什么說線性原献、非線性，暫時我沒有深入去研究了埂淮。

基數(shù)排序

算法思想

基數(shù)排序的核心思想是多關鍵字排序姑隅。
通常有兩種實現(xiàn)，一叫做最高位優(yōu)先倔撞，即先按最高位排成若干子序列讲仰，再對每個子序列按次高位排序。以撲克牌為例误窖，現(xiàn)按花色排序叮盘，再按同一花色的13張排序，改變排序的關鍵字要素霹俺，不停變化柔吼，最終使得整個序列有序。另一種交最低位優(yōu)先丙唧，這種方式不必劃分子序列愈魏，每次排序全體關鍵字都參加，最低位通過“分配”想际、“收集”方式培漏，而不是通過比較。比如撲克牌先按數(shù)字分配到13個桶里面胡本，然后從第一個桶開始依次收集牌柄，再將收集好的牌按花色分配到4個桶中，然后還是從第一個桶開始依次收集侧甫。經(jīng)過量詞“分配”珊佣、“收集”操作，最終使得序列有序披粟。

基數(shù)排序第一輪.PNG

基數(shù)排序第二輪.PNG

最后一輪排序我就不畫圖了咒锻，繼續(xù)遞推下去，可以看到整組序列就有序了守屉。整個過程未做比較操作惑艇，只是做了分類操作。所以排序不一定只是比較拇泛，思維上的突破往往是最難的滨巴。

時間復雜度

基排序的復雜度為O(d(n+Rd))， 其中n為序列中的關鍵字個數(shù)俺叭，d為關鍵字的子位數(shù)兢卵，例如數(shù)字125，d就是3绪颖，Rd為關鍵字基（構成關鍵字的符號秽荤，例如關鍵字為數(shù)值時，構成關鍵字的符號可以選擇0-9柠横，即Rd=10）的個數(shù)窃款。這個推理過程比較難以記錄，我在一本書上找到了一個更加直觀的理解記憶方法牍氛，如下：
基數(shù)排序每一趟都要進行“分配”晨继、“收集”操作，分配需要一次對序列中的每個關鍵字進行搬俊，即需要掃描整個序列紊扬，所以有n這一項蜒茄；“收集”需要一次對每個桶進行，二桶的數(shù)量取決于關鍵字的取值范圍餐屎，如果放數(shù)字的桶有10個檀葛，放花色的桶有4個，所以就存在Rd這一項腹缩，因此屿聋，一趟“分配”、“收集”需要的時間n+Rd藏鹊。那整個排序需要多少趟呢润讥？有多少個關鍵字，就有多少趟盘寡，即需要d趟楚殿。

空間復雜度

每個桶實際上就是一個隊列，需要頭尾指針竿痰，共Rd個桶勒魔，所以需要2Rd個指針，即空間復雜度O（Rd）菇曲。

適用場景

基數(shù)排序適合序列中的關鍵字比較多冠绢，但是組成關鍵字的取值范圍較小，即桶的數(shù)量較少的情況下常潮。

桶排序

算法思想

將數(shù)組分到有限數(shù)量的桶子里弟胀，每個桶子再分別排序（有可能再使用別的[排序算法]或是以遞歸方式繼續(xù)使用桶排序進行排序）。
桶排序的思路很簡單喊式，但是在實際使用中通常需要考慮以下因素：
1）元素到桶的映射規(guī)則孵户，需要合理的將n和元素分都m個桶，合理性與業(yè)務邏輯強相關岔留。
2）桶內數(shù)據(jù)排序算法的選擇夏哭，可以根據(jù)相關數(shù)據(jù)集合的特征，選擇排序算法献联，也可以繼續(xù)采用桶排序遞歸竖配。
這個具體的設計過程與原始數(shù)據(jù)有很強的相關性，而這部分設計正是“你也懂算法里逆，我也懂算法进胯，但是我做的東西就是比你好的原因”。對于原始數(shù)據(jù)的研究和理解原押，以及先有計算能力的評估和衡量胁镐，是利用好一個算法的關鍵。

總結

排序算法總結.PNG

下一章將討論外部排序內容，外部排序又是另外一種風景盯漂。