????????排序算法可以分為內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進行排序,不需要訪問外存便能完成. 而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。用一張圖概括：
????????外部排序點擊以下圖片查看大圖：
????關(guān)于時間復(fù)雜度
????????平方階 (O(n2)) 排序 各類簡單排序：直接插入、直接選擇和冒泡排序。
????????線性對數(shù)階 (O(nlog2n)) 排序 快速排序、堆排序和歸并排序；
????????O(n1+§)) 排序，§ 是介于 0 和 1 之間的常數(shù)。 希爾排序
????????線性階 (O(n)) 排序 基數(shù)排序，此外還有桶、箱排序。
????關(guān)于穩(wěn)定性
????????穩(wěn)定的排序算法：冒泡排序、插入排序、歸并排序和基數(shù)排序。
????????不是穩(wěn)定的排序算法：選擇排序、快速排序、希爾排序、堆排序。
????名詞解釋：
? ? ? ? n：數(shù)據(jù)規(guī)模
????????k："桶"的個數(shù)
????????In-place：占用常數(shù)內(nèi)存，不占用額外內(nèi)存
????????Out-place：占用額外內(nèi)存
????????穩(wěn)定性：排序后 2 個相等鍵值的順序和排序之前它們的順序相同
1. 冒泡排序 BubbleSort
????????冒泡排序是一種交換排序。
????????什么是交換排序呢？
? ? ? ? ——?兩兩比較待排序的關(guān)鍵字，并交換不滿足次序要求的那對數(shù)，直到整個表都滿足次序要求為止。
????????它重復(fù)地走訪要排序的數(shù)列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。
????????這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端，故名冒泡排序。
? ??????動態(tài)效果示意圖：
????????假設(shè)有一個大小為 N 的無序序列。以升序冒泡排序為例，冒泡排序就是要每趟排序過程中通過兩兩比較相鄰元素，將小的數(shù)字放到前面，大的數(shù)字放在后面。
算法分析
1、冒泡排序算法的性能
2、時間復(fù)雜度
????????若文件的初始狀態(tài)是正序的，一趟掃描即可完成排序。所需的關(guān)鍵字比較次數(shù)C和記錄移動次數(shù)M均達(dá)到最小值：Cmin = N - 1, Mmin = 0。所以，冒泡排序最好時間復(fù)雜度為O(N)。
????????但是上述代碼，不能掃描一趟就完成排序，它會進行全掃描。所以一個改進的方法就是，當(dāng)冒泡中途發(fā)現(xiàn)已經(jīng)為正序了，便無需繼續(xù)比對下去。改進方法一會兒介紹。
????????若初始文件是反序的，需要進行 N -1 趟排序。每趟排序要進行 N - i 次關(guān)鍵字的比較(1 ≤ i ≤ N - 1)，且每次比較都必須移動記錄三次來達(dá)到交換記錄位置。在這種情況下，比較和移動次數(shù)均達(dá)到最大值：
????????Cmax = N(N-1)/2 = O(N^2)
????????Mmax = 3N(N-1)/2 = O(N^2)
????????冒泡排序的最壞時間復(fù)雜度為O(N^2)。
????????因此，冒泡排序的平均時間復(fù)雜度為O(N^2)。
????????總結(jié)起來，其實就是一句話：當(dāng)數(shù)據(jù)越接近正序時，冒泡排序性能越好。
????3. 算法穩(wěn)定性
????????假定在待排序的記錄序列中，存在多個具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。
????????冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。是相鄰的兩個元素的比較，交換也發(fā)生在這兩個元素之間。所以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩(wěn)定排序算法。
????4. 優(yōu)化
????????對冒泡排序常見的改進方法是加入標(biāo)志性變量exchange，用于標(biāo)志某一趟排序過程中是否有數(shù)據(jù)交換。
????????如果進行某一趟排序時并沒有進行數(shù)據(jù)交換，則說明所有數(shù)據(jù)已經(jīng)有序，可立即結(jié)束排序，避免不必要的比較過程。
2. 快速排序?Quicksort
????????快速排序是一種交換排序，它由C. A. R. Hoare在1962年提出?？焖倥判?quick sort)的采用了分而治之(divide and conquer)的策略：將原問題分解為若干個規(guī)模更小但結(jié)構(gòu)與原問題相似的子問題。遞歸地解這些子問題，然后將這些子問題的解組合為原問題的解。
????1. 算法思想
????????快速排序的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分：分割點左邊都是比它小的數(shù)，右邊都是比它大的數(shù)。
????????然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達(dá)到整個數(shù)據(jù)變成有序序列。
? ??????動態(tài)效果示意圖：
????????詳細(xì)的圖解往往比大堆的文字更有說明力，所以直接上圖：
????????上圖中，演示了快速排序的處理過程：
? ??????初始狀態(tài)為一組無序的數(shù)組：2、4、5、1、3。
????????經(jīng)過以上操作步驟后，完成了第一次的排序，得到新的數(shù)組：1、2、5、4、3。
????????新的數(shù)組中，以2為分割點，左邊都是比2小的數(shù)，右邊都是比2大的數(shù)。
????????因為2已經(jīng)在數(shù)組中找到了合適的位置，所以不用再動。
????????2左邊的數(shù)組只有一個元素1，所以顯然不用再排序，位置也被確定。（注：這種情況時，left指針和right指針顯然是重合的。因此在代碼中，我們可以通過設(shè)置判定條件left必須小于right，如果不滿足，則不用不用不用不不用不用不用不用不用用不用排序了）。
????????而對于2右邊的數(shù)組5、4、3，設(shè)置left指向5，right指向3，開始繼續(xù)重復(fù)圖中的一、二、三、四步驟，對新的數(shù)組進行排序。
????快排的工作過程其實比較簡單，三步走：
? ? ? ? a. 選擇基準(zhǔn)值 pivot 將數(shù)組分成兩個子數(shù)組：小于基準(zhǔn)值的元素和大于基準(zhǔn)值的元素。這個過程稱之為 partition
? ? ? ? b. 對這兩個子數(shù)組進行快速排序。
? ? ? ? c. 合并結(jié)果,遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
????2. 代碼+結(jié)果
????3. 算法分析
? ? ? ? 3.1 快速排序算法的性能
? ? ? ? 3.2 時間復(fù)雜度
????????當(dāng)數(shù)據(jù)有序時，以第一個關(guān)鍵字為基準(zhǔn)分為兩個子序列，前一個子序列為空，此時執(zhí)行效率最差。
????????而當(dāng)數(shù)據(jù)隨機分布時，以第一個關(guān)鍵字為基準(zhǔn)分為兩個子序列，兩個子序列的元素個數(shù)接近相等，此時執(zhí)行效率最好。
????????所以，數(shù)據(jù)越隨機分布時，快速排序性能越好；數(shù)據(jù)越接近有序，快速排序性能越差。
????????3.3 時間復(fù)雜度
????????快速排序在每次分割的過程中，需要 1 個空間存儲基準(zhǔn)值。而快速排序的大概需要 logN次的分割處理，所以占用空間也是 logN 個。
????3.4 算法穩(wěn)定性
????????在快速排序中，相等元素可能會因為分區(qū)而交換順序，所以它是不穩(wěn)定的算法。
3. 直接插入排序 Straight Insertion Sort
????????直接插入排序（Insertion Sort）序是一種最簡單的插入排序。為簡化問題，我們下面只討論升序排序。
? ? 1. 算法思想
? ??????插入排序：每一趟將一個待排序的記錄，按照其關(guān)鍵字的大小插入到有序隊列的合適位置里，知道全部插入完成。?
? ??????動態(tài)效果示意圖：
????????以上的過程，其實就是典型的直接插入排序，每次將一個新數(shù)據(jù)插入到有序隊列中的合適位置里。
????????很簡單吧，接下來，我們要將這個算法轉(zhuǎn)化為編程語言。
????????假設(shè)有一組無序序列 R0, R1, ... , RN-1。
????????(1) 我們先將這個序列中下標(biāo)為 0 的元素視為元素個數(shù)為 1 的有序序列。
????????(2) 然后，我們要依次把 R1, R2, ... , RN-1 插入到這個有序序列中。所以，我們需要一個外部循環(huán)，從下標(biāo) 1 掃描到 N-1 。
????????(3) 接下來描述插入過程。假設(shè)這是要將 Ri 插入到前面有序的序列中。由前面所述，我們可知，插入Ri時，前 i-1 個數(shù)肯定已經(jīng)是有序了。
????????所以我們需要將Ri 和R0 ~ Ri-1 進行比較，確定要插入的合適位置。這就需要一個內(nèi)部循環(huán)，我們一般是從后往前比較，即從下標(biāo) i-1 開始向 0 進行掃描。
2. 代碼+答案
3. 算法分析
? ? 3.1 直接插入排序的算法性能
????3.2 時間復(fù)雜度
????????當(dāng)數(shù)據(jù)正序時，執(zhí)行效率最好，每次插入都不用移動前面的元素，時間復(fù)雜度為O(N)。?
????????當(dāng)數(shù)據(jù)反序時，執(zhí)行效率最差，每次插入都要前面的元素后移，時間復(fù)雜度為O(N^2)。
????????所以，數(shù)據(jù)越接近正序，直接插入排序的算法性能越好。?
????3.3 空間復(fù)雜度
????????由直接插入排序算法可知，我們在排序過程中，需要一個臨時變量存儲要插入的值，所以空間復(fù)雜度為 1 。
? ? 3.4 算法穩(wěn)定性
????????直接插入排序的過程中，不需要改變相等數(shù)值元素的位置，所以它是穩(wěn)定的算法。?
????4. 優(yōu)化
????????因為在一個有序序列中查找一個插入位置，以保證有序序列的序列不變，所以可以使用二分查找，減少元素比較次數(shù)提高效率。
????????二分查找是對于有序數(shù)組而言的，假設(shè)如果數(shù)組是升序排序的。那么，二分查找算法就是不斷對數(shù)組進行對半分割，每次拿中間元素和目標(biāo)數(shù)字進行比較，如果中間元素小于目標(biāo)數(shù)字，則說明目標(biāo)數(shù)字應(yīng)該在右側(cè)被分割的數(shù)組中，如果中間元素大于目標(biāo)數(shù)字，則說明目標(biāo)數(shù)字應(yīng)該在左側(cè)被分割的數(shù)組中。
4. 希爾排序
? ??????希爾(Shell)排序又稱為縮小增量排序，它是一種插入排序。它是直接插入排序算法的一種威力加強版。
????????希爾排序，也稱遞減增量排序算法，以其設(shè)計者希爾（Donald Shell）的名字命名，該算法由 1959 年公布。
? ? 1. 算法思想
????????我們舉個例子來描述算法流程（以下摘自維基百科）：
????????假設(shè)有這樣一組數(shù) {13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10}，如果我們以步長為 5 開始進行排序：
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
? ??????然后我們對每列進行排序：
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
? ??????將上述四行數(shù)字，依序接在一起時我們得到：{10, 14, 73, 25, 23, 13, 27, 94, 33, 39, 25, 59, 94, 65, 82, 45}，然后再以 3 為步長：
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
????????排序之后變?yōu)椋?/p>
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
????????最后以 1 為步長進行排序（此時就是簡單的插入排序了）。
????????可想而知，步長的選擇是希爾排序的重要部分。算法最開始以一定的步長進行排序，然后會繼續(xù)以更小的步長進行排序，最終算法以步長為 1 進行排序。當(dāng)步長為 1 時，算法變?yōu)橹苯硬迦肱判?，這就保證了數(shù)據(jù)一定會被全部排序。
????????下面以n/2作為步長為例進行講解。(步長自己取)
算法分析
? ? ?希爾排序的算法性能
? ? 1. 時間復(fù)雜度
????????步長的選擇是希爾排序的重要部分，只要最終步長為1任何步長序列都可以工作。
????????算法最開始以一定的步長進行排序。然后會繼續(xù)以一定步長進行排序，最終算法以步長為1進行排序。當(dāng)步長為1時，算法變?yōu)椴迦肱判?，這就保證了數(shù)據(jù)一定會被排序。
? ??????步長序列的不同，會導(dǎo)致最壞的時間復(fù)雜度情況的不同。
????????本文中，以N/2為步長的最壞時間復(fù)雜度為N^2。
????????Donald Shell?最初建議步長選擇為N/2并且對步長取半直到步長達(dá)到1。雖然這樣取可以比O(N^2)類的算法（插入排序）更好，但這樣仍然有減少平均時間和最差時間的余地。可能希爾排序最重要的地方在于當(dāng)用較小步長排序后，以前用的較大步長仍然是有序的。比如，如果一個數(shù)列以步長5進行了排序然后再以步長3進行排序，那么該數(shù)列不僅是以步長3有序，而且是以步長5有序。如果不是這樣，那么算法在迭代過程中會打亂以前的順序，那就不會以如此短的時間完成排序了。
????????用這樣步長序列的希爾排序比插入排序要快，甚至在小數(shù)組中比快速排序和堆排序還快，但是在涉及大量數(shù)據(jù)時希爾排序還是比快速排序慢。
? ? 2. 算法穩(wěn)定性
????????希爾排序中相等數(shù)據(jù)可能會交換位置，所以希爾排序是不穩(wěn)定的算法。
? ? 3. 直接插入排序和希爾排序的比較
????????直接插入排序是穩(wěn)定的；而希爾排序是不穩(wěn)定的。
????????直接插入排序更適合于原始記錄基本有序的集合。
????????希爾排序的比較次數(shù)和移動次數(shù)都要比直接插入排序少，當(dāng)N越大時，效果越明顯。??
????????希爾排序的比較次數(shù)和移動次數(shù)都要比直接插入排序少，當(dāng)N越大時，效果越明顯。??
????????直接插入排序也適用于鏈?zhǔn)酱鎯Y(jié)構(gòu)；希爾排序不適用于鏈?zhǔn)浇Y(jié)構(gòu)。
5. 簡單選擇排序
? ??????簡單選擇排序是一種選擇排序。
? ??????選擇排序：每趟從待排序的記錄中選出關(guān)鍵字最小的記錄，順序放在已排序的記錄序列末尾，直到全部排序結(jié)束為止。
????1. 算法思想
????????簡單排序很簡單，它的大致處理流程為：
????????從待排序序列中，找到關(guān)鍵字最小的元素；
????????如果最小元素不是待排序序列的第一個元素，將其和第一個元素互換；
????????從余下的?N - 1?個元素中，找出關(guān)鍵字最小的元素，重復(fù)(1)、(2)步，直到排序結(jié)束。
? ??????動態(tài)效果示意圖：
????????舉例說明，處理過程示意圖如下所示：
????????如圖所示，每趟排序中，將當(dāng)前第?i?小的元素放在位置?i?上。
????2. 代碼+結(jié)果
3. 算法分析
????3.1 簡單算法排序性能
????????其中，N2為N^2。
? ? 3.2 時間復(fù)雜度
????????簡單選擇排序的比較次數(shù)與序列的初始排序無關(guān)。?假設(shè)待排序的序列有?N?個元素，則比較次數(shù)總是N (N - 1) / 2。
????????而移動次數(shù)與序列的初始排序有關(guān)。當(dāng)序列正序時，移動次數(shù)最少，為?0.
????????當(dāng)序列反序時，移動次數(shù)最多，為3N (N - 1) /? 2。
????????所以，綜合以上，簡單排序的時間復(fù)雜度為O(N^2)。
? ? 3.3 空間復(fù)雜度
????????簡單選擇排序需要占用1個臨時空間，用于保存最小值得索引。
6. 堆排序
????????堆排序是一種選擇排序。
? ??????選擇排序：每趟從待排序的記錄中選出關(guān)鍵字最小的記錄，順序放在已排序的記錄序列末尾，直到全部排序結(jié)束為止。
1. 算法思想
????????堆排序是利用堆的性質(zhì)進行的一種選擇排序。
? ??????動態(tài)效果示意圖：
? ??????堆是一棵順序存儲的完全二叉樹。
????????其中每個結(jié)點的關(guān)鍵字都不大于其孩子結(jié)點的關(guān)鍵字，這樣的堆稱為小根堆。
????????其中每個結(jié)點的關(guān)鍵字都不小于其孩子結(jié)點的關(guān)鍵字，這樣的堆稱為大根堆。
????????舉例來說，對于n個元素的序列{R0, R1, ... , Rn}當(dāng)且僅當(dāng)滿足下列關(guān)系之一時，稱之為堆：
????????Ri?<= R2i+1?且?Ri?<= R2i+2?(小根堆)
????????Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)
????????其中i=1,2,…,n/2向下取整；
????????如上圖所示，序列R{3, 8, 15, 31, 25}是一個典型的小根堆。
????????堆中有兩個結(jié)點，元素3和元素8。
????????元素3在數(shù)組中以R[0]表示，它的左孩子結(jié)點是R[1]，右孩子結(jié)點是R[2]。
????????元素8在數(shù)組中以R[1]表示，它的左孩子結(jié)點是R[3]，右孩子結(jié)點是R[4]，它的父結(jié)點是R[0]?？梢钥闯?，它們滿足以下規(guī)律：
????設(shè)當(dāng)前元素在數(shù)組中以R[i]表示，那么，
????????(1)?它的左孩子結(jié)點是：R[2*i+1];
????????(2)?它的右孩子結(jié)點是：R[2*i+2];
????????(3)?它的父結(jié)點是：R[(i-1)/2];
????????(4) R[i] <= R[2*i+1]?且?R[i] <= R[2i+2]。
????????首先，按堆的定義將數(shù)組R[0..n]調(diào)整為堆（這個過程稱為創(chuàng)建初始堆），交換R[0]和R[n]；
????????然后，將R[0..n-1]調(diào)整為堆，交換R[0]和R[n-1]；
????????如此反復(fù)，直到交換了R[0]和R[1]為止。
????????以上思想可歸納為兩個操作：
????????（1）根據(jù)初始數(shù)組去構(gòu)造初始堆（構(gòu)建一個完全二叉樹，保證所有的父結(jié)點都比它的孩子結(jié)點數(shù)值大）。
????????（2）每次交換第一個和最后一個元素，輸出最后一個元素（最大值），然后把剩下元素重新調(diào)整為大根堆。
????????當(dāng)輸出完最后一個元素后，這個數(shù)組已經(jīng)是按照從小到大的順序排列了。
????????先通過詳細(xì)的實例圖來看一下，如何構(gòu)建初始堆。
????????設(shè)有一個無序序列?{ 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 }。
????????構(gòu)造了初始堆后，我們來看一下完整的堆排序處理：
????????還是針對前面提到的無序序列?{ 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 }?來加以說明。
? ? ? ? ?比如如下數(shù)組?{57, 40, 38, 11, 13, 34, 48, 75, 6, 19, 9, 7}堆排序前如下：
進行堆排序后如下：
? ? ? ? 最大堆的存儲結(jié)構(gòu)如下：
? ??????接著，最后一步，堆排序，進行（n-1）次循環(huán)。
?????????相信，通過以上兩幅圖，應(yīng)該能很直觀的演示堆排序的操作處理。?
????????看完上面所述的流程你至少有一個疑問：
? ??如何確定最后一個非葉子結(jié)點？
????????其實這是有一個公式的，設(shè)二叉樹結(jié)點總數(shù)為 n，則最后一個非葉子結(jié)點是第?n/2?個。
3. 算法分析
? ? 3.1 堆排序算法的總體情況
? ? 3.2 時間復(fù)雜度
????????首先計算建堆的時間，也就是下面的代碼，
// 循環(huán)建立初始堆
for (int i = length / 2; i >= 0; i--){
HeapAdjust(list, i, length);
}
????????n 個結(jié)點，從第 0 層至第logn層。對于第 i 層的2i個點如果需要往下走logn?i步，那么把走的所有步相加得：
????????接下來就是排序的時間，即下面的代碼：
// 進行n-1次循環(huán)，完成排序
for (int i = length - 1; i > 0; i--){
// 最后一個元素和第一元素進行交換
int temp = list[i];
list[i] = list[0];
list[0] = temp;
// 篩選 R[0] 結(jié)點，得到i-1個結(jié)點的堆
HeapAdjust(list, 0, i);
}
????????HeapAdjust() 耗時logn，共 n 次，故排序時間為O(nlogn)。
????????堆的存儲表示是順序的。因為堆所對應(yīng)的二叉樹為完全二叉樹，而完全二叉樹通常采用順序存儲方式。
????????當(dāng)想得到一個序列中第k個最小的元素之前的部分排序序列，最好采用堆排序。
????3.3 算法穩(wěn)定性
????????堆排序是一種不穩(wěn)定的排序方法。
????????因為在堆的調(diào)整過程中，關(guān)鍵字進行比較和交換所走的是該結(jié)點到葉子結(jié)點的一條路徑，因此對于相同的關(guān)鍵字就可能出現(xiàn)排在后面的關(guān)鍵字被交換到前面來的情況。?
7. 歸并排序 MergeSort
????????歸并排序是建立在歸并操作上的一種有效的排序算法，該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。
1. 算法思想
????????該算法采用經(jīng)典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然后遞歸求解，而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之)。
? ??????動態(tài)效果示意圖：
? ??????分而治之：
????????1. 分階段
????????可以看到這種結(jié)構(gòu)很像一棵完全二叉樹，本文的歸并排序我們采用遞歸去實現(xiàn)（也可采用迭代的方式去實現(xiàn)）。分階段可以理解為就是遞歸拆分子序列的過程，遞歸深度為logn。
????????2. 治階段
????????再來看看治階段，我們需要將兩個已經(jīng)有序的子序列合并成一個有序序列，比如上圖中的最后一次合并，要將[4,5,7,8]和[1,2,3,6]兩個已經(jīng)有序的子序列，合并為最終序列[1,2,3,4,5,6,7,8]，來看下實現(xiàn)步驟。
3. 算法分析
????3.1. 歸并排序算法的性能
????????其中，log2n為以2為底，n的對數(shù)。
????3.2 時間復(fù)雜度
????????歸并排序的形式就是一棵二叉樹，它需要遍歷的次數(shù)就是二叉樹的深度，而根據(jù)完全二叉樹的可以得出它的時間復(fù)雜度是O(n*log2n)。
????3.3 空間復(fù)雜度
????????由前面的算法說明可知，算法處理過程中，需要一個大小為n的臨時存儲空間用以保存合并序列。
????3.4 算法穩(wěn)定性
????????在歸并排序中，相等的元素的順序不會改變，所以它是穩(wěn)定的算法。
????3.5 歸并排序和堆排序、快速排序的比較
????????若從空間復(fù)雜度來考慮：首選堆排序，其次是快速排序，最后是歸并排序。
????????若從穩(wěn)定性來考慮，應(yīng)選取歸并排序，因為堆排序和快速排序都是不穩(wěn)定的。
????????若從平均情況下的排序速度考慮，應(yīng)該選擇快速排序。?
8. 基數(shù)排序 RadixSort
????????基數(shù)排序是一種非比較型整數(shù)排序算法，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個位數(shù)分別比較。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)。
1. 算法思想
????????基本思想：將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長度，數(shù)位較短的數(shù)前面補零。然后，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以后,數(shù)列就變成一個有序序列。
????????算法步驟：
????????將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長度，數(shù)位較短的數(shù)前面補零。
????????從最低位開始，依次進行一次排序。
????????這樣從最低位排序一直到最高位排序完成以后, 數(shù)列就變成一個有序序列。
? ? ? ? 基數(shù)排序的方式可以采用 LSD（Least significant digital）或 MSD（Most significant digital），LSD 的排序方式由鍵值的最右邊開始，而 MSD 則相反，由鍵值的最左邊開始。
????????不妨通過一個具體的實例來展示一下基數(shù)排序是如何進行的。 設(shè)有一個初始序列為: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。
????????我們知道，任何一個阿拉伯?dāng)?shù)，它的各個位數(shù)上的基數(shù)都是以 0~9 來表示的，所以我們不妨把 0~9 視為 10 個桶。
????????我們先根據(jù)序列的個位數(shù)的數(shù)字來進行分類，將其分到指定的桶中。例如：R[0] = 50，個位數(shù)上是 0，將這個數(shù)存入編號為 0 的桶中。
????????分類后，我們在從各個桶中，將這些數(shù)按照從編號 0 到編號 9 的順序依次將所有數(shù)取出來。這時，得到的序列就是個位數(shù)上呈遞增趨勢的序列。
????????按照個位數(shù)排序： {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}。
????????接下來，可以對十位數(shù)、百位數(shù)也按照這種方法進行排序，最后就能得到排序完成的序列。
? ??????動態(tài)效果示意圖：
3. 算法分析
????3.1 基數(shù)排序的性能
????????其中，d代表數(shù)組元素最高為位數(shù)，n代表元素個數(shù)。
????3.2 時間復(fù)雜度
????????這個時間復(fù)雜度比較好計算：count * length；其中 count 為數(shù)組元素最高位數(shù)，length為元素個數(shù)；所以時間復(fù)雜度：O(n * d)
????3.3 空間復(fù)雜度
????????空間復(fù)雜度是使用了兩個臨時的數(shù)組：10 + length；所以空間復(fù)雜度：O（n）。
????3.4 算法穩(wěn)定性
? ? ? ? 在基數(shù)排序過程中，每次都是將當(dāng)前位數(shù)上相同數(shù)值的元素統(tǒng)一“裝桶”，并不需要交換位置。所以基數(shù)排序是穩(wěn)定的算法。
