排序算法

因為一直在做應用開發的緣故，自大學學習了<code>資料結構和算法</code>後，就較少使用到算法的知識，大多使用程式設計語言自帶的排序方法。最近項目時間相對寬裕，就想再次拾起那遺落在角落的排序算法知識。

<code>冒泡排序</code>是我最先接觸的排序算法，記得大一老師開始講解這個算法的時候，通過循序漸進的講解，在最後還特地帶我們對這個算法進行了簡單的優化，那時感覺，原來算法是這麼好玩。但這個優化卻并沒有多大的效率改善，但因時間複雜度擺在這裡，效率也是墊底的。這個排序算法也是最容易了解的。

排序算法可以分為内部排序和外部排序，内部排序是資料記錄在記憶體中進行排序，而外部排序是因排序的資料很大，一次不能容納全部的排序記錄，在排序過程中需要通路外存。常見的内部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。用一張圖概括：

平方階 (o(n2)) 排序 各類簡單排序：直接插入、直接選擇和冒泡排序。

線性對數階 (o(nlog2n)) 排序 快速排序、堆排序和歸并排序；

o(n1+§)) 排序，§ 是介于 0 和 1 之間的常數。 希爾排序

線性階 (o(n)) 排序 基數排序，此外還有桶、箱排序。

<code>穩定的排序算法</code>：冒泡排序、插入排序、歸并排序和基數排序。

<code>不是穩定的排序算法</code>：選擇排序、快速排序、希爾排序、堆排序。

<code>n</code>：資料規模

<code>k</code>：“桶”的個數

<code>in-place</code>：占用常數記憶體，不占用額外記憶體

<code>out-place</code>：占用額外記憶體

<code>穩定性</code>：排序後 2 個相等鍵值的順序和排序之前它們的順序相同