各種内部排序的總結

前面已經把基本的内部排序分别介紹了下，現在總結一下各種排序友善在筆試的時候能做出正确的答案。排序剛開始的時候都是簡單排序:冒泡排序、直接插入排序、簡單選擇排序。随後開始了對前面3種簡單排序的改進分别對應的是快速排序、希爾排序、堆排序。改進的地方是：冒泡排序是交換類排序最初的原型，他的思想是從兩兩比較相鄰的關鍵字若是逆序則交換。思路比較直接，每一趟就可以找到一個最大的元素缺點在于交換的次數實在太多。快速排序的改進則是比較的不再是相鄰的元素而是一個key，并且采用分治的政策。簡單選擇排序也感覺是對冒泡排序的改進，冒泡排序的缺點在于頻繁的交換，按照《大話資料結構》裡的比喻是冒泡排序好比炒股時的短期持有，頻繁的買入賣出的手續費以及印花稅導緻了即使不出錯也很難有很大的盈利。比較有經驗的會看準時機果斷買入賣出。這種比喻是表明簡單選擇排序的特點是每趟排序僅僅隻是做一次交換。但是它的缺點在于每一趟排序都沒有記憶前一趟排序的結果，于是後面的排序要做一些前面已經做過的比較。堆排序是對簡單選擇排序的改進，它采用的方法就是将序列建成一個堆(實際上可能不一定是這種結構，是用下标模拟的)用于記錄關鍵字之間的相對關系。直接插入排序的想法是将序列分為有序序列和無序序列，初始化時有序序列為第一個元素，從無序序列中選擇第一個元素插入到有序序列中直到無序序列為空。希爾排序是對直接插入排序的改進，改進的依據是在關鍵字數量較小或者基本有序時直接插入排序的效率非常高，是以希爾排序的思想就是構造這兩個條件：關鍵字數量小可以想到用分組的政策這樣就會把關鍵字的數量成倍的縮小，基本有序采用的方法是讓分組不斷減小當小到一定程度(這裡一般分組為1時)時便可以達到，然後進行直接插入排序就可以了。若是關鍵字較少簡單排序要優于改進排序，原因在于改進排序用了很多時間和空間來轉化問題。具體的分類記憶表格：

排序種類	簡單排序	改進排序
交換排序	冒泡排序	快速排序
插入排序	直接插入排序	希爾排序
選擇排序	簡單選擇排序	堆排序

所有排序的時間複雜度和空間複雜度、穩定性

排序法	最好時間複雜度	最壞時間複雜度	平均時間複雜度	穩定性
冒泡排序	O(n)	O(n^2)	O(n^2)	穩定
直接插入排序	O(n)	O(n^2)	O(n^2)	穩定
簡單選擇排序	O(n^2)	O(n^2)	O(n^2)	穩定
快速排序	O(n*logn)	O(n^2)	O(n*logn)	不穩定
希爾排序	O(n^1.3)	O(n^2)	O(n*logn~n^2)	不穩定

堆排序

O(n*logn)

O(n*logn)

O(n*logn)

不穩定