本文将對于插入排序、冒泡排序、選擇排序、希爾排序、歸并排序、快速排序、堆排序、配置設定排序和基數排序做歸納總結，通過一些題目來掌握各大内部排序算法的過程和特點，而不涉及具體的代碼。
考點
- 排序算法的穩定性（題1）
- 排序算法的空間效率（題2）
- 特殊資料下排序算法的效率比較 / 算法的最差、平均、最佳情況（題3、8、9）
- 排序算法的執行過程（題4、5、6、7、10）
習題
1、當排序的序列存在多個具有相同關鍵碼的記錄時，經過排序後，如果這些記錄的相對順序仍然保持不變，則這個排序算法稱為是穩定的。八種内部排序法哪些是穩定的，如果不穩定，如何修改使之穩定？
【答案】
插入排序、冒泡排序是穩定的。 因為元素交換當且僅當元素大小為嚴格的不等關系。
選擇排序不穩定。 因為它僅當目前元素比目前最小元素小時才重新設定最小元素值，但是檢索是從數組末尾開始的，是以可能會出現相同值的元素順序改變。對于這個算法隻需将選擇最小關鍵碼的條件從”小于”改為”小于等于”即可。
希爾排序不穩定。 因為子表的排序是互相獨立的，很可能在子表中發生的交換使得一個元素移到了與它等值的元素的前面。
快速排序不穩定。 選擇好樞紐後将樞紐與數組中最後一個元素交換，這個過程是不需要條件的，可能恰好交換了兩個值相同的元素。
歸并排序理論上是穩定的。 但是它的數組實作不穩定，當兩個子表的第一個元素相同時，歸并操作會優先選擇其中一個子表的元素。隻需将選擇的條件從“小于”改為“小于等于”即可。
堆排序不穩定。 左右子樹的元素的處理時互相獨立的，這很可能使得元素原來的相對位置發生改變。
配置設定排序是穩定的。 相同的元素總是被添加到清單的末尾，不發生次序的變化。
基數排序是穩定的。 因為桶的填充過程和處理序列取出元素過程都是自底向上的，保持了相對順序。
2、在下列排序算法中，所需輔助存儲量最多的是（）
A) 快速排序 B) 歸并排序 C) 堆排序 D) 鍊式基數排序
【分析】
由于快速排序和堆排序是原地排序，不需要輔助數組，故排除。歸并排序隻需要與原數組等大的輔助數組即可，鍊式基數排序每位數排序時都需要開辟與原數組數目相同的連結清單結點空間，所需輔助存儲量最多，故選D。
原地排序
指基本上不需要額外輔助的的空間，允許少量額外的輔助變量進行的排序。就是在原來的排序數組中比較和交換的排序。像選擇排序，插入排序，希爾排序，快速排序，堆排序等都會有一項比較且交換操作(swap(i,j))的邏輯在其中，是以他們都是屬于原地(原址、就地)排序，而合并排序，計數排序，基數排序等不是原地排序。
3、在檔案“局部有序”或檔案長度較小的情況下，最佳内部排序的方法是（）
A) 直接插入排序 B) 冒泡排序 C) 簡單選擇排序 D) 基數排序
【分析】
比較一下插入排序、冒泡排序、選擇排序：
| 插入排序 | 冒泡排序 | 選擇排序 |
|---|---|---|
| k輪後前k個元素有序 | k輪後前k大(小)的元素已排好 | k輪後前k大(小)的元素已排好 |
| 排序可以提前結束，如果數組已然有序隻需要O(n)的時間複雜度 | 排序不可提前結束(最佳情況仍為O(n^2)) | 排序不可提前結束 |
由上，此題選A。
【補充】
交換排序算法的關鍵瓶頸是比較操作次數，時間複雜度統計的是比較操作次數
| 比較情況 | 插入排序 | 冒泡排序 | 選擇排序 |
|---|---|---|---|
| 最佳情況 | O(n) | O(n^2) | O(n^2) |
| 平均情況 | O(n^2) | O(n^2) | O(n^2) |
| 最差情況 | O(n^2) | O(n^2) | O(n^2) |
交換操作可以決定一個算法實際效率
| 交換情況 | 插入排序 | 冒泡排序 | 選擇排序 |
|---|---|---|---|
| 最佳情況 | O(n) | ||
| 平均情況 | O(n^2) | O(n^2) | O(n) |
| 最差情況 | O(n^2) | O(n^2) | O(n) |
4、資料表中有10000個元素，如果僅需求出其中最大的10個元素，則采用（）排序算法最節省時間。
A) 快速排序 B) 希爾排序 C) 堆排序 D) 選擇排序
【分析】
挑選10個最大的元素故聚焦堆排序和選擇排序，由于堆排序是O(nlogn)，選擇排序是O(n^2)，故選C。
5、資料序列(8,9,10,4,5,6,20,1,2)隻能是下列排序算法中的（）兩趟排序後的結果。
A) 選擇排序 B) 冒泡排序 C) 插入排序 D) 堆排序
【分析】
根據前面的總結，冒泡排序和選擇排序的兩輪排序後前兩個元素是一樣的，插入排序與前兩者的差別就在于它隻保證了有序，但無需是最大的或最小的。是以由于前兩個元素是升序排序，如果是冒泡或者是選擇那麼前兩個元素應該是整個數組中最小的兩個元素，顯然不對，故選C。
6、對一組資料(84,47,25,15,21)排序，資料的排列次序在排序的過程中的變化為
(1) 84 47 25 15 21 (2) 15 47 25 84 21 (3) 15 21 25 84 47 (4) 15 21 25 47 84
則采用的排序是（）
A) 選擇排序 B) 冒泡排序 C) 快速排序 D) 插入排序
【分析】
觀察知，排序可能為冒泡或選擇，選擇和冒泡的差別主要在于一輪排序中的交換次數，是以隻需觀察排序過程中序列的變化程度就能做出判斷。具體的看，選擇排序在每輪隻發生一次交換，觀察序列知此題選A。
7、對序列(15,9,7,8,20,-1,4)進行排序，進行一趟後資料的排列變為(4,9,-1,8,20,7,15)；則采用的是（）排序。
A) 選擇排序 B) 快速排序 C) 希爾排序 D) 冒泡排序
【分析】
希爾排序需要知道縮小增量是多少故不選。選擇排序和冒泡排序都要求局部排好，而一輪過後的序列的第一個元素既不是最大也不是最小，故不選。是以選C。可以發現pivot大概選擇的是8。
【補充】希爾排序
Shell排序是這樣進行分組和排序的：把序列分成多個“虛拟”子序列然後分别對子序列進行排序。子序列的排序則利用插入排序。
分割子序列的具體方法是從整個數組中等間距地抽取元素。每輪排序都會縮小間距（增量）。
選擇适當的增量序列可以使Shell排序比其他排序方法更有效率。一般來說增量序列為(2k,2k-1,…,2,1)時2并無多大效果，而“增量每次除以3”更好。
希爾排序的時間複雜度為O(n^1.5)，可能有疑問是，如果Shell排序總是以一個正常的插入排序結束，又怎會比插入排序的效率更高？希爾排序希望經過每次對子序列的處理，可以使待排序的數組更加有序，當最後一輪調用插入排序時，數組已經是基本有序的了，并産生一個相對花費時間較少的最終插入排序（前文有提到插入排序提前結束的性質）。
注：當資料規模中等時，希爾排序具有很好的效率。
8、下列排序算法中，在待排序資料已有序時，花費時間反而最多的是（）排序。
A) 冒泡排序 B) 希爾排序 C) 快速排序 D) 堆排序
【分析】
考察各内部排序算法的最差情況，快速排序的退化。選C。
【快速排序的退化】
快速排序是迄今為止所有内部排序算法中在平均情況下最快的一種。相比于歸并排序，快速排序不需要額外的數組空間，是以空間效率也很高。但有意思的是，快速排序往往由于最差時間代價而在某些應用中無法采用。
快速排序最差情況出現在軸值未能很好地劃分數組的時候，即一個子數組中沒有結點，而另一個數組中有n-1個結點。在這種情況下，分治政策未能很好地完成劃分任務。是以，下一次處理的子問題規模隻比原問題的規模減少了1個元素。如果這種情況發生在每一次劃分過程中，那麼算法的總時間代價為O(n^2)。由于遞歸調用的時間開銷，這甚至比冒泡排序更糟糕。
9、對初始狀态為遞增序列的表按遞增順序排序，最省時間的是（）算法，最費時間的是（）算法。
A) 歸并排序 B) 快速排序 C) 插入排序 D) 堆排序
【分析】
考察排序算法處理特殊資料的效率。選C ; B。
10、幾種重要排序算法的過程
【堆排序】
題目：将整數數組（7-6-3-5-4-1-2）按照堆排序的方式原地進行升序排列，請問在第一輪排序結束後，數組的順序是（）
A.2-6-3-5-4-1-7
B.6-2-3-5-4-1-7
C.6-5-3-2-4-1-7
D.1-5-3-2-4-6-7
E.5-4-3-2-1-6-7
F.5-1-3-2-4-6-7
答案：C
解析：因為是原地進行升序排列，是以應該是建立大根堆；如果是原地進行降序排列，應該建立小根堆。
第一步：先建立大根堆，因為給定的數組就是大根堆，是以就不需要建立大根堆了。大根堆圖如下：
第二步：堆建好之後開始排序，堆頂就是最大值，取出放入數組中的最後一個位置，将堆底（數組中的最後一個元素）放入堆頂。因為這一操作會破壞堆，需要将前n-1個元素調整為堆。這樣一輪排序就結束了。
調整為大根堆之後：
是以在第一輪排序結束後，數組的順序是：6-5-3-2-4-1-7
題目2：給出一組關鍵字T=(12,2,16,30,8,28,4,10,20,6,18)。寫出用下列算法從小到大排序時第一趟結束時的序列。
【希爾排序】（第一趟排序的增量為6）
答案：（4,2,16,6,8,28,12,10,20,30,18）
【快速排序】（選第一個記錄為樞軸）
先交換第一個元素和最後一個元素，再用兩個指針從頭和尾向中間并攏，分别找大于軸值的元素和小于軸值的元素，都找到了則交換，直至兩個指針指向同一個元素（右部的首元素），傳回左指針的值，并将該位置的元素和尾元素交換，一輪排序完畢。
答案：（6,2,10,4,8,12,30,16,20,18,28）