? ? 眾所周知，排序算法在數(shù)據(jù)結(jié)構(gòu)中是很重要的，而排序又分為內(nèi)部排序（待排序記錄存放在計算機(jī)存儲器中進(jìn)行的排序過程）和外部排序（由于待排序記錄數(shù)量大呛牲，以致內(nèi)存一次不能容納全部記錄鞍恢，在排序過程中需要對外存進(jìn)行訪問）希太。本篇文章主要描述內(nèi)部排序狼速。內(nèi)部排序可以分為（大的方面5類，小的方面8類）：插入排序（直接插入排序卦停、希爾排序）向胡、選擇排序（簡單選擇排序、堆排序）惊完、交換排序（冒泡排序僵芹、快速排序）、歸并排序小槐、基數(shù)排序拇派；以下對這8類排序算法進(jìn)行一一詳細(xì)說明。
注：排序算法的穩(wěn)定性定義如下--->
1凿跳、直接插入排序：
思想：首先將序列的第一個記錄看成是一個有序的子序列件豌，然后從第二個記錄開始逐個進(jìn)行插入，直至整個序列有序為止控嗜。
注意：設(shè)立哨兵茧彤，作為臨時存儲和判斷數(shù)組邊界之用。
程序代碼：
時間復(fù)雜度：O（n^2）,特別情況下疆栏， 當(dāng)所要排序的數(shù)據(jù)是有序的情況下曾掂，時間復(fù)雜度變?yōu)楦玫腛(n);
空間復(fù)雜度：O（1）惫谤；
穩(wěn)定性：穩(wěn)定
2、希爾排序：
思想：先將整個待排序記錄序列分割成若干個子序列分別進(jìn)行直接插入排序珠洗，待整個序列中的記錄“基本有序”時溜歪，再對全體記錄進(jìn)行依次直接插入排序。
注意：分割子序列是通過增量因子進(jìn)行分割的许蓖，增量因子選取時蝴猪，應(yīng)注意它除了1外沒有公因子，且最后一個增量因子必為1蛔糯。
程序代碼：
時間復(fù)雜度：O（n^1.3）---O(n^1.5)
空間復(fù)雜度：O（1）
穩(wěn)定性：不穩(wěn)定
3拯腮、簡單選擇排序：
思想：在要排序的一組數(shù)中，選出最幸响（或者最大）的一個數(shù)與第一個位置的數(shù)進(jìn)行交換动壤，然后在剩下的數(shù)中再找最小（或者最大）的與第二個位置的數(shù)交換淮逻，依次類推琼懊，直至第n-1個元素（倒數(shù)第二個數(shù)）與第n個元素(最后一個數(shù))比較為止。
注意：第一趟爬早，從n個記錄中選出關(guān)鍵碼最小的記錄與第一個記錄進(jìn)行交換哼丈；第二趟，從第二個記錄開始的n-1個記錄里選出關(guān)鍵碼最小的記錄與第二個記錄進(jìn)行交換筛严；.......第i趟醉旦，從第i個記錄開始的n-i+1個記錄中選出關(guān)鍵碼最小的記錄與第i個記錄進(jìn)行交換。
程序代碼：
時間復(fù)雜度：O（n^2）
空間復(fù)雜度：O（1）
穩(wěn)定性：不穩(wěn)定
4桨啃、堆排序：
思想：首先需要建立大根堆（父>子）或者小根堆（父<子）车胡，這樣就得到了最大值或者最小值（即堆頂元素），此時將堆頂元素與堆中最后一個元素進(jìn)行交換照瘾，再對最后一個元素除外的所有元素進(jìn)行大根堆或者小根堆的重新調(diào)整匈棘。這樣直到所有元素都調(diào)整完畢，就得到了一個有序序列的記錄析命。
注意：父-->子：n-->2*n+1 ,2*n+2 ;子-->父：n-->(n-1)/2
構(gòu)造大根堆（小根堆）：第一次構(gòu)造大根堆（小根堆）主卫，需要從最后一顆子樹開始，從后往前多次調(diào)整鹃愤，每次調(diào)整的過程是從上往下簇搅。
程序代碼：
時間復(fù)雜度：O（nlog2^n）(log以2為底n的對數(shù))（注：一次堆調(diào)整的時間復(fù)雜度是O（log2^n））
空間復(fù)雜度：O（1）
穩(wěn)定性：不穩(wěn)定
拓：堆排序的前身是錦標(biāo)排序（樹形選擇排序），它的時間復(fù)雜度是O(nlog2^n),空間復(fù)雜度（O（n））软吐，是穩(wěn)定的馍资，但是它因為占用太多的輔助空間，所以不推薦使用，下面是錦標(biāo)排序的思想圖:
5鸟蟹、冒泡排序：
思想：在要排序的一組數(shù)中乌妙，自上而下的對相鄰的兩個數(shù)依次進(jìn)行比較和調(diào)整，較大的數(shù)往下沉建钥，較小的數(shù)往上冒藤韵。
程序代碼:
時間復(fù)雜度：O（n^2）
空間復(fù)雜度：O（1）
穩(wěn)定性：穩(wěn)定
冒泡排序優(yōu)化:
6、快速排序：
思想：
遞歸的快速排序-->先在待排序的記錄中選擇一個數(shù)（通常是第一個數(shù)或者最后一個數(shù)）作為基準(zhǔn)熊经，設(shè)立兩個指向標(biāo)記泽艘，分別指向第一個元素和最后一個元素，然后進(jìn)行第一趟劃分镐依，若最后一個數(shù)大于或等于基準(zhǔn)值匹涮，則使指向最后一個數(shù)的指向標(biāo)記向前移動；若最后一個數(shù)小于基準(zhǔn)值槐壳，則將最后一個數(shù)與第一個數(shù)進(jìn)行交換然低，此時將指向第一個數(shù)的指向標(biāo)記向前移動。則第一趟得到的記錄剛好以基準(zhǔn)值為分界線务唐，以上述同樣的方法再對分界線兩邊的部分進(jìn)行排序,基準(zhǔn)值就等于說找到了最終位置雳攘。
非遞歸的快速排序-->主要是利用棧來存儲兩個指向標(biāo)記的值，其它與遞歸的快速排序不相上下枫笛。
程序代碼:
1.遞歸的快速排序:
2.非遞歸的快速排序:
時間復(fù)雜度：O（nlog2^n）注：快速排序數(shù)據(jù)越有序吨灭，時間復(fù)雜度越大，性能越不好刑巧。
空間復(fù)雜度：O（log2^n）
穩(wěn)定性：不穩(wěn)定
7喧兄、歸并排序：
思想：將兩個（或者兩個以上）的有序表合并成一個新的有序表，即把待排序序列分為若干個子序列啊楚，每個子序列都是有序的吠冤。然后再把有序子序列合并為整體有序序列。
程序代碼：
時間復(fù)雜度：O（nlog2^n）
空間復(fù)雜度：O（n）
穩(wěn)定性：穩(wěn)定
8特幔、基數(shù)排序：
思想：【低位優(yōu)先，鏈?zhǔn)疥犃小空⒆颍瑢?shù)字按位數(shù)劃分出n個關(guān)鍵字蚯斯，每次針對一個關(guān)鍵字進(jìn)行排序，然后針對排序后的序列進(jìn)行下個關(guān)鍵字的排序饵较，循環(huán)至所有關(guān)鍵字都是用過拍嵌，則排序完成。
程序代碼：建立下標(biāo)為0--9的隊列循诉，然后依次按關(guān)鍵字（低位優(yōu)先）將數(shù)據(jù)入隊横辆，然后再出隊。直至所有數(shù)據(jù)都排完茄猫。
時間復(fù)雜度：O（d*n）d代表數(shù)字的個數(shù)狈蚤，n代表要排序的數(shù)的總數(shù)
空間復(fù)雜度：O（n）
穩(wěn)定性：穩(wěn)定
排序算法時間,空間復(fù)雜度匯總:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?end ? ? ? ?2016 5 27
