亂序.PNG

上面的同學(xué)請(qǐng)保持秩序。。。本章，來(lái)研究一下排序算法。
排序算法在大部分情況下并不具備直接商業(yè)應(yīng)用的條件，但是對(duì)我們理解排序的本質(zhì)思想是非常有幫助的，正所謂萬(wàn)變不離其宗。所以關(guān)于排序算法，我也更多的是先從舉一反三的思考問(wèn)題的角度去復(fù)習(xí)。

排序算法大全

排序算法.PNG

排序算法的評(píng)估要素

1.穩(wěn)定性：穩(wěn)定性與實(shí)現(xiàn)方式有很強(qiáng)的相關(guān)性，但是如果是按相對(duì)最優(yōu)（教科書(shū)）的算法步驟實(shí)現(xiàn)，每種算法的穩(wěn)定性是固定的。
2.時(shí)間復(fù)雜度：與算法的數(shù)學(xué)思想強(qiáng)相關(guān)。例如二分的思想，遞歸的思想，遍歷的思想
3.空間復(fù)雜度：內(nèi)存與資源的開(kāi)銷，可以針對(duì)不同場(chǎng)景提供不同的算法

插入類

直接插入排序

算法思想

每一次遍歷，將一個(gè)待排序關(guān)鍵字（只要是沒(méi)有被處理的關(guān)鍵字即可）按照其值的大小插入到已經(jīng)排好的部分有序序列中，插入方式取決于排序方式（從小到大，則按照從小到大方式插入到有序序列中），直到所有關(guān)鍵字都被插入到有序序列為。
該算法的核心思想：“大事化小，以0為起始”。
該算法比較簡(jiǎn)單，就不提供圖示樣例了，腦補(bǔ)一下。

時(shí)間復(fù)雜度

該算法存在兩個(gè)步驟：
1--遍歷全部關(guān)鍵字，這個(gè)是必不可少的
2--插入操作，所以需要對(duì)已排序序列做移動(dòng)，移動(dòng)次數(shù)與原序列的“有序度（原序列與目標(biāo)序列的初始匹配度）”有關(guān)
所以算法復(fù)雜度，平均是n（step1）*n（step2），即O(n2)；最壞的情況下，step2每次要移動(dòng)全部已排序序列，所以會(huì)導(dǎo)致最壞復(fù)雜度為也是O(n2)；最好的情況下，step2不需要做任何操作，新的關(guān)鍵字插入有序序列的時(shí)候，不需要對(duì)原有序序列做操作，即最好情況為O(n)。

空間復(fù)雜度

插入動(dòng)作過(guò)程中我們需要一個(gè)temp用來(lái)存儲(chǔ)關(guān)鍵字，所以通?？臻g復(fù)雜度為O(1)。如果崗警說(shuō)，我搞個(gè)temp[n]，然后拷貝有序序列。。那我想說(shuō)，也可以，但是不標(biāo)準(zhǔn)。

穩(wěn)定性

思考一下，排序前后的序列，對(duì)重復(fù)的關(guān)鍵字是否會(huì)有變化呢？一般可以以舉反例的方式來(lái)推理。比如有一個(gè)序列 3 1 1 5 2 2 9，按照從小到大排序。第二個(gè)1在插入的時(shí)候，如果插入在第一個(gè)1之前，那么這個(gè)實(shí)現(xiàn)就不穩(wěn)定排序，但是如果插入在第二個(gè)（即最后一個(gè)重復(fù)關(guān)鍵字）之后就算是穩(wěn)定的。然而，上述反例是偽證。因?yàn)槲覀儾豢赡苤雷詈笠粋€(gè)重復(fù)關(guān)鍵字在哪，如果要遍歷，那就不是O(n2)的復(fù)雜度了。所以通常的合理實(shí)現(xiàn)，應(yīng)當(dāng)是選擇插入在第一個(gè)1前面，所以我認(rèn)為直接插入排序的實(shí)現(xiàn)一定是不穩(wěn)定，盡管理論上具備穩(wěn)定的可能性。

折半插入排序

算法思想

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

算法復(fù)雜度

折半插入排序減少了比較元素的次數(shù)，約為O(nlogn)，比較的次數(shù)取決于表的元素個(gè)數(shù)n。因此，折半插入排序的時(shí)間復(fù)雜度仍然為O(n2)，所以當(dāng)數(shù)據(jù)量有一定規(guī)模的情況下，該算法會(huì)表現(xiàn)出遠(yuǎn)優(yōu)于直接插入的性能。

希爾排序

算法思想

希爾排序又叫做縮小量排序，其本質(zhì)還是插入排序，特別之處在于將待排序序列按某種規(guī)則分成幾個(gè)子序列，分別對(duì)幾個(gè)子序列進(jìn)行直接插入排序。規(guī)則的關(guān)鍵在于增量的選擇，如果增量為1，就是直接插入排序。說(shuō)了這么多，來(lái)看個(gè)實(shí)例吧

希爾排序.PNG

時(shí)間復(fù)雜度

按照希爾的方案選取增量，那么對(duì)于n序列長(zhǎng)度的排序，最壞情況下為O(n的平方)，當(dāng)n在某個(gè)特定范圍時(shí)，約為O(n的1.3次方)
關(guān)于希爾排序算法復(fù)雜度的證明過(guò)程比較復(fù)雜，待后續(xù)有時(shí)間再詳解。

空間復(fù)雜度

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

穩(wěn)定性

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

交換類

冒泡排序

算法思想

此處略去100字。

時(shí)間復(fù)雜度

因?yàn)橐鰞蓚€(gè)循環(huán)才能完成全部冒泡，所以時(shí)間復(fù)雜度O(n的平方)

空間復(fù)雜度

只需要一個(gè)temp即可，O(1)；

穩(wěn)定性

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

快速排序

算法思想

快速排序也是交換類排序，他通過(guò)“多次劃分”實(shí)現(xiàn)排序操作。已升序?yàn)槔?，?zhí)行流程如下
1）選擇1個(gè)當(dāng)前子序列的關(guān)鍵字作為軸，通常從第一個(gè)關(guān)鍵字開(kāi)始
2）將大于關(guān)鍵字的放在右邊，小于關(guān)鍵字的放在左邊，經(jīng)過(guò)一輪循環(huán)后，中軸關(guān)鍵字的左邊為一個(gè)序列，右邊為一個(gè)序列
3）當(dāng)遍歷完一輪全部數(shù)據(jù)后，全部數(shù)據(jù)將會(huì)被分為兩組，然后本輪循環(huán)結(jié)束。假如你沒(méi)看過(guò)教科書(shū)的灌輸思維，這里應(yīng)該如何去判定“全部數(shù)據(jù)完成一次遍歷”這個(gè)操作呢？
4）分別對(duì)左邊序列和右邊序列執(zhí)行1、2、3操作，直到子序列為1個(gè)元素為止。

快排.PNG

時(shí)間復(fù)雜度

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

空間復(fù)雜度

直觀來(lái)看，快排只用了一個(gè)temp，所以空間復(fù)雜度應(yīng)該是O(1)，然后快排的實(shí)現(xiàn)是遞歸，遞歸是需要?？臻g開(kāi)銷的，空間復(fù)雜度等于遞歸次數(shù)*O(1)，即O(nlog2n)。

穩(wěn)定性

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

選擇類

簡(jiǎn)單選擇排序

算法思想

我認(rèn)為這是世界上最直觀最簡(jiǎn)單的算法，連小朋友打撲克都會(huì)的算法。
找出最小的放在第一位，次小放在第二位，再次放在第三位，依次排序。。還有啥比這更簡(jiǎn)單的嗎

時(shí)間復(fù)雜度

直接插入排序就兩步 1）找到最小，需要輪詢 2）放到對(duì)應(yīng)的位置，需要將已有序列統(tǒng)一向后挪動(dòng)，等于插隊(duì)，其他人往后站，依然需要輪詢已有序列，兩遍輪詢，時(shí)間復(fù)雜度O(n的平方)；，，
這里要注意，直接插入排序和直接選擇排序的區(qū)別，雖然都有插入這個(gè)動(dòng)作，但是前者是移動(dòng)有序序列，后者是挪動(dòng)無(wú)序序列讓出空間。這兩者有直接區(qū)別，所以閱讀代碼的時(shí)候，不要看到insert就想到一定是插入排序了。

空間復(fù)雜度

挪動(dòng)過(guò)程，并不需要新建數(shù)組，所以空間復(fù)雜度O(1);

穩(wěn)定性

序列在發(fā)生交換的時(shí)候，會(huì)改變?cè)邢嗤P(guān)鍵字的順序，所以選擇排序是不穩(wěn)定的。
例如7，8，7，3，9，7和3交換以后，兩個(gè)7的相對(duì)位置已經(jīng)發(fā)生了變化。

堆排序

（在這個(gè)階段提堆排序會(huì)感覺(jué)有點(diǎn)跳躍性，直接從一個(gè)超級(jí)簡(jiǎn)單的算法到了一個(gè)較為復(fù)雜的算法，但是沒(méi)辦法。。選擇排序只有這兩種）

背景知識(shí)補(bǔ)齊

因?yàn)槲以谒惴ㄟ@部分并沒(méi)有考慮再去討論數(shù)據(jù)結(jié)構(gòu)了，但是這里這個(gè)算法用到了堆，所以再把堆相關(guān)的知識(shí)拿出來(lái)復(fù)習(xí)一下。
堆是一種基本數(shù)據(jù)結(jié)構(gòu)，可以將其理解為一個(gè)完全二叉樹(shù)，而這顆二叉樹(shù)滿足：任何一個(gè)非葉節(jié)點(diǎn)值都不大于(或不小于)其左右孩子節(jié)點(diǎn)的值。若父親大孩子小，稱為大頂堆；父親小孩子大稱為小頂堆。由此可見(jiàn)，如果以大頂堆為例，根節(jié)點(diǎn)就是該序列最大值。

算法思想

利用堆的特征，將待排序序列構(gòu)成一個(gè)大頂堆，然后移除根節(jié)點(diǎn)，將剩余節(jié)點(diǎn)再轉(zhuǎn)化成一個(gè)大頂堆，一次完成排序操作。
問(wèn)題1：如何將無(wú)序序列轉(zhuǎn)化為大頂堆
問(wèn)題2：將堆頂元素挪走以后，如何將剩余元素繼續(xù)做成大頂堆。是重復(fù)問(wèn)題1的解法去遞歸，還是另有方法。
如果很想深究上述兩個(gè)問(wèn)題的答案，建議充分復(fù)習(xí)一下二叉樹(shù)和完全二叉樹(shù)的數(shù)據(jù)結(jié)構(gòu)。我這里給出上述兩個(gè)問(wèn)題的解法。
排序步驟如下：
1）將無(wú)序序列轉(zhuǎn)化成一個(gè)完全二叉樹(shù)，如圖

堆.PNG

2）對(duì)該完全二叉樹(shù)從第一個(gè)非葉節(jié)點(diǎn)開(kāi)始從右至左從下往上堆每個(gè)節(jié)點(diǎn)進(jìn)行調(diào)整
調(diào)整方法：將該節(jié)點(diǎn)的值域其孩子節(jié)點(diǎn)比較，如果有大于該節(jié)點(diǎn)的孩子節(jié)點(diǎn)，則從中選出最大的一個(gè)與該節(jié)點(diǎn)進(jìn)行交換。該節(jié)點(diǎn)如果存在多層的孩子，則需要層層往下執(zhí)行上述步驟，至到該節(jié)點(diǎn)的所有孩子均小于該節(jié)點(diǎn)。
3）完成2以后，得到一個(gè)大頂堆。將根節(jié)點(diǎn)與最小的葉子節(jié)點(diǎn)交換（這么做也是為了最小化內(nèi)存空間占用，和前面的排序思想一樣。做算法設(shè)計(jì)，必須精益求精，做到極致，算法是小杠桿，一點(diǎn)點(diǎn)開(kāi)銷堆整個(gè)產(chǎn)業(yè)帶來(lái)的可能就是巨大的成本浪費(fèi)），這樣將整棵樹(shù)分為有序和無(wú)序兩部分。對(duì)于無(wú)序部分，再次執(zhí)行上述2)步驟。直到無(wú)序隊(duì)列只剩最后一個(gè)元素。還是用圖來(lái)說(shuō)明這個(gè)過(guò)程。

1.PNG

2.PNG

時(shí)間復(fù)雜度

算法復(fù)雜度為O(nlog2n)，至于怎么來(lái)的，我會(huì)在算法基礎(chǔ)2.2中實(shí)現(xiàn)堆排序的代碼，屆時(shí)用代碼來(lái)解釋上述圖中復(fù)雜的節(jié)點(diǎn)遷移變化的時(shí)間開(kāi)銷。
這里有一點(diǎn)需要明確，堆排序如此復(fù)雜，為什么還要用它。?？赡艽蠹乙呀?jīng)意識(shí)到，堆排序是一個(gè)二叉樹(shù)遍歷問(wèn)題，二叉樹(shù)的遍歷，最好最壞時(shí)間復(fù)雜度都是O(nlog2n)，而快排的最壞復(fù)雜度是O(n的平方)。所以，當(dāng)數(shù)據(jù)量很大但是卻只需要找出排名前幾的關(guān)鍵字時(shí)，堆排序有較為明顯的優(yōu)勢(shì)。
比如考試成績(jī)排名，需要在20W考生里面找到廣東省排名前100的，快排就會(huì)比較耗時(shí)，堆排序優(yōu)勢(shì)明顯。

空間復(fù)雜度

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

穩(wěn)定性

在舉個(gè)例子說(shuō)明：8 17(a) 26 17(b)，
如果堆頂8先輸出，17(b)跑到堆頂，然后堆穩(wěn)定，繼續(xù)輸出堆頂，即17(b)，于是17(b)出現(xiàn)在了17(a)前面，不穩(wěn)定。
理論過(guò)程描述：
堆的特征是節(jié)點(diǎn)i的孩子為2 * i和2 * i + 1節(jié)點(diǎn)，大頂堆要求父節(jié)點(diǎn)大于等于其2個(gè)子節(jié)點(diǎn)。于是，對(duì)于一個(gè)n 序列，堆排序的過(guò)程是從第n / 2開(kāi)始和其子節(jié)點(diǎn)共3個(gè)值選擇最大（大頂堆），這3個(gè)元素之間的選擇不會(huì)破壞穩(wěn)定性。但當(dāng)為n / 2 - 1， n / 2 - 2， ... 1這些個(gè)父節(jié)點(diǎn)選擇元素時(shí)，就會(huì)破壞穩(wěn)定性。有可能第n / 2個(gè)父節(jié)點(diǎn)交換把后面一個(gè)元素交換過(guò)去了，而第n / 2 - 1個(gè)父節(jié)點(diǎn)把后面一個(gè)相同的元素沒(méi)有交換，那么這2個(gè)相同的元素之間的穩(wěn)定性就被破壞了。所以，堆排序不是穩(wěn)定的排序算法。

歸并類

歸并排序

算法思想

歸并排序是一個(gè)分治的過(guò)程：先將整個(gè)序列分為兩半，堆每一辦進(jìn)行歸并排序，將得到兩個(gè)有序序列，然后將兩個(gè)有序序列合并為一個(gè)即可。其實(shí)，歸并算法的關(guān)鍵點(diǎn)分裂和合并。
來(lái)看個(gè)圖

分裂.PNG

合并.PNG

時(shí)間復(fù)雜度

歸并排序的時(shí)間復(fù)雜度，用數(shù)學(xué)歸納來(lái)推導(dǎo)一下。
第一趟歸并需要執(zhí)行2(n/2)=n次基本操作（其中2為子序列關(guān)鍵字的個(gè)數(shù)之和，n/2為要?dú)w并的子序列堆的個(gè)數(shù)，每個(gè)子序列對(duì)執(zhí)行一次merge操作，也就是兩次(比較+交換)基本操作）
第二趟歸并需要執(zhí)行4(n/4)=n
第三趟歸并需要執(zhí)行8(n/8)=n
第k趟歸并需要執(zhí)行2的k次方(n/2的k次方)=n
……………………
當(dāng)n/2的k次方 = 1時(shí)，即需要?dú)w并的兩個(gè)子序列長(zhǎng)度均為原序列的一半時(shí)，歸并排序結(jié)束，此時(shí)k=log2n，即總共需要log2n趟排序，時(shí)間復(fù)雜度為O(nlog2n)

空間復(fù)雜度

歸并過(guò)程中，我們需要轉(zhuǎn)儲(chǔ)整個(gè)序列，所以空間復(fù)雜度為O(n)

穩(wěn)定性

可以想象，兩個(gè)項(xiàng)目的元素，在分裂和合并過(guò)程中，并不會(huì)發(fā)生相對(duì)位置的變化。所以歸并排序是穩(wěn)定的。

線性時(shí)間比較類

怎么突然冒出一個(gè)線性時(shí)間呢？其實(shí)前面的所有排序都是非線性時(shí)間比較類排序。
非線性時(shí)間比較排序--基于比較的排序，其算法時(shí)間復(fù)雜度不能突破O（nlogn）。
線性時(shí)間比較排序--不基于比較的排序，其算法時(shí)間復(fù)雜度可以突破O（nlogn）。
至于為什么說(shuō)線性、非線性，暫時(shí)我沒(méi)有深入去研究了。

基數(shù)排序

算法思想

基數(shù)排序的核心思想是多關(guān)鍵字排序。
通常有兩種實(shí)現(xiàn)，一叫做最高位優(yōu)先，即先按最高位排成若干子序列，再對(duì)每個(gè)子序列按次高位排序。以撲克牌為例，現(xiàn)按花色排序，再按同一花色的13張排序，改變排序的關(guān)鍵字要素，不停變化，最終使得整個(gè)序列有序。另一種交最低位優(yōu)先，這種方式不必劃分子序列，每次排序全體關(guān)鍵字都參加，最低位通過(guò)“分配”、“收集”方式，而不是通過(guò)比較。比如撲克牌先按數(shù)字分配到13個(gè)桶里面，然后從第一個(gè)桶開(kāi)始依次收集，再將收集好的牌按花色分配到4個(gè)桶中，然后還是從第一個(gè)桶開(kāi)始依次收集。經(jīng)過(guò)量詞“分配”、“收集”操作，最終使得序列有序。

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

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

最后一輪排序我就不畫圖了，繼續(xù)遞推下去，可以看到整組序列就有序了。整個(gè)過(guò)程未做比較操作，只是做了分類操作。所以排序不一定只是比較，思維上的突破往往是最難的。

時(shí)間復(fù)雜度

基排序的復(fù)雜度為O(d(n+Rd))， 其中n為序列中的關(guān)鍵字個(gè)數(shù)，d為關(guān)鍵字的子位數(shù)，例如數(shù)字125，d就是3，Rd為關(guān)鍵字基（構(gòu)成關(guān)鍵字的符號(hào)，例如關(guān)鍵字為數(shù)值時(shí)，構(gòu)成關(guān)鍵字的符號(hào)可以選擇0-9，即Rd=10）的個(gè)數(shù)。這個(gè)推理過(guò)程比較難以記錄，我在一本書(shū)上找到了一個(gè)更加直觀的理解記憶方法，如下：
基數(shù)排序每一趟都要進(jìn)行“分配”、“收集”操作，分配需要一次對(duì)序列中的每個(gè)關(guān)鍵字進(jìn)行，即需要掃描整個(gè)序列，所以有n這一項(xiàng)；“收集”需要一次對(duì)每個(gè)桶進(jìn)行，二桶的數(shù)量取決于關(guān)鍵字的取值范圍，如果放數(shù)字的桶有10個(gè)，放花色的桶有4個(gè)，所以就存在Rd這一項(xiàng)，因此，一趟“分配”、“收集”需要的時(shí)間n+Rd。那整個(gè)排序需要多少趟呢？有多少個(gè)關(guān)鍵字，就有多少趟，即需要d趟。

空間復(fù)雜度

每個(gè)桶實(shí)際上就是一個(gè)隊(duì)列，需要頭尾指針，共Rd個(gè)桶，所以需要2Rd個(gè)指針，即空間復(fù)雜度O（Rd）。

適用場(chǎng)景

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

桶排序

算法思想

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

總結(jié)

排序算法總結(jié).PNG

下一章將討論外部排序內(nèi)容，外部排序又是另外一種風(fēng)景。