? ? 眾所周知，排序算法在數(shù)據(jù)結(jié)構(gòu)中是很重要的，而排序又分為內(nèi)部排序（待排序記錄存放在計算機存儲器中進行的排序過程）和外部排序（由于待排序記錄數(shù)量大，以致內(nèi)存一次不能容納全部記錄，在排序過程中需要對外存進行訪問）。本篇文章主要描述內(nèi)部排序。內(nèi)部排序可以分為（大的方面5類，小的方面8類）：插入排序（直接插入排序、希爾排序）、選擇排序（簡單選擇排序、堆排序）、交換排序（冒泡排序、快速排序）、歸并排序、基數(shù)排序；以下對這8類排序算法進行一一詳細說明。
注：排序算法的穩(wěn)定性定義如下--->
1、直接插入排序：
思想：首先將序列的第一個記錄看成是一個有序的子序列，然后從第二個記錄開始逐個進行插入，直至整個序列有序為止。
注意：設(shè)立哨兵，作為臨時存儲和判斷數(shù)組邊界之用。
程序代碼：
時間復雜度：O（n^2）,特別情況下， 當所要排序的數(shù)據(jù)是有序的情況下，時間復雜度變?yōu)楦玫腛(n);
空間復雜度：O（1）；
穩(wěn)定性：穩(wěn)定
2、希爾排序：
思想：先將整個待排序記錄序列分割成若干個子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。
注意：分割子序列是通過增量因子進行分割的，增量因子選取時，應(yīng)注意它除了1外沒有公因子，且最后一個增量因子必為1。
程序代碼：
時間復雜度：O（n^1.3）---O(n^1.5)
空間復雜度：O（1）
穩(wěn)定性：不穩(wěn)定
3、簡單選擇排序：
思想：在要排序的一組數(shù)中，選出最?。ɑ蛘咦畲螅┑囊粋€數(shù)與第一個位置的數(shù)進行交換，然后在剩下的數(shù)中再找最?。ɑ蛘咦畲螅┑呐c第二個位置的數(shù)交換，依次類推，直至第n-1個元素（倒數(shù)第二個數(shù)）與第n個元素(最后一個數(shù))比較為止。
注意：第一趟，從n個記錄中選出關(guān)鍵碼最小的記錄與第一個記錄進行交換；第二趟，從第二個記錄開始的n-1個記錄里選出關(guān)鍵碼最小的記錄與第二個記錄進行交換；.......第i趟，從第i個記錄開始的n-i+1個記錄中選出關(guān)鍵碼最小的記錄與第i個記錄進行交換。
程序代碼：
時間復雜度：O（n^2）
空間復雜度：O（1）
穩(wěn)定性：不穩(wěn)定
4、堆排序：
思想：首先需要建立大根堆（父>子）或者小根堆（父<子），這樣就得到了最大值或者最小值（即堆頂元素），此時將堆頂元素與堆中最后一個元素進行交換，再對最后一個元素除外的所有元素進行大根堆或者小根堆的重新調(diào)整。這樣直到所有元素都調(diào)整完畢，就得到了一個有序序列的記錄。
注意：父-->子：n-->2*n+1 ,2*n+2 ;子-->父：n-->(n-1)/2
構(gòu)造大根堆（小根堆）：第一次構(gòu)造大根堆（小根堆），需要從最后一顆子樹開始，從后往前多次調(diào)整，每次調(diào)整的過程是從上往下。
程序代碼：
時間復雜度：O（nlog2^n）(log以2為底n的對數(shù))（注：一次堆調(diào)整的時間復雜度是O（log2^n））
空間復雜度：O（1）
穩(wěn)定性：不穩(wěn)定
拓：堆排序的前身是錦標排序（樹形選擇排序），它的時間復雜度是O(nlog2^n),空間復雜度（O（n）），是穩(wěn)定的，但是它因為占用太多的輔助空間，所以不推薦使用，下面是錦標排序的思想圖:
5、冒泡排序：
思想：在要排序的一組數(shù)中，自上而下的對相鄰的兩個數(shù)依次進行比較和調(diào)整，較大的數(shù)往下沉，較小的數(shù)往上冒。
程序代碼:
時間復雜度：O（n^2）
空間復雜度：O（1）
穩(wěn)定性：穩(wěn)定
冒泡排序優(yōu)化:
6、快速排序：
思想：
遞歸的快速排序-->先在待排序的記錄中選擇一個數(shù)（通常是第一個數(shù)或者最后一個數(shù)）作為基準，設(shè)立兩個指向標記，分別指向第一個元素和最后一個元素，然后進行第一趟劃分，若最后一個數(shù)大于或等于基準值，則使指向最后一個數(shù)的指向標記向前移動；若最后一個數(shù)小于基準值，則將最后一個數(shù)與第一個數(shù)進行交換，此時將指向第一個數(shù)的指向標記向前移動。則第一趟得到的記錄剛好以基準值為分界線，以上述同樣的方法再對分界線兩邊的部分進行排序,基準值就等于說找到了最終位置。
非遞歸的快速排序-->主要是利用棧來存儲兩個指向標記的值，其它與遞歸的快速排序不相上下。
程序代碼:
1.遞歸的快速排序:
2.非遞歸的快速排序:
時間復雜度：O（nlog2^n）注：快速排序數(shù)據(jù)越有序，時間復雜度越大，性能越不好。
空間復雜度：O（log2^n）
穩(wěn)定性：不穩(wěn)定
7、歸并排序：
思想：將兩個（或者兩個以上）的有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列都是有序的。然后再把有序子序列合并為整體有序序列。
程序代碼：
時間復雜度：O（nlog2^n）
空間復雜度：O（n）
穩(wěn)定性：穩(wěn)定
8、基數(shù)排序：
思想：【低位優(yōu)先，鏈式隊列】，將數(shù)字按位數(shù)劃分出n個關(guān)鍵字，每次針對一個關(guān)鍵字進行排序，然后針對排序后的序列進行下個關(guān)鍵字的排序，循環(huán)至所有關(guān)鍵字都是用過，則排序完成。
程序代碼：建立下標為0--9的隊列，然后依次按關(guān)鍵字（低位優(yōu)先）將數(shù)據(jù)入隊，然后再出隊。直至所有數(shù)據(jù)都排完。
時間復雜度：O（d*n）d代表數(shù)字的個數(shù)，n代表要排序的數(shù)的總數(shù)
空間復雜度：O（n）
穩(wěn)定性：穩(wěn)定
排序算法時間,空間復雜度匯總:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?end ? ? ? ?2016 5 27
