## 前言
早上重新整理聞時看到了排序演算法， 今天就來說說我所知道用到的一些排序演算法。
## 排序演算法
### 冒泡
最經典的排序演算法了， 它最思想就是相鄰的兩個數對比， 並保證， 他們的順序是按目標順序排列的。
例子， 我們要從小到大。 過程如下：
```
1 4 5 3 2 // 原始佇列
1 4 5 3 2 // 1 與 4 不同交換
1 4 5 3 2 // 4 與 5 也不同交換
1 4 3 5 2 // 5 與 3 需要交換
1 4 3 2 5 // 5 與 2 需要交換
// 到這裡一輪結束， 同時可以注意到最時最大的 5 已經到最後的位置了， 下一輪在前 4 個數中再重複上面的步驟即可
。。。。
```
說明： 冒泡一直在做的事就是讓相鄰的兩個數滿足目標的大小關係（左大於右， 還是右大於左）。
其實在每一輪的過程中， 就會有一個數找到它的位置。
在資料的比較中， 要注意一個地方就是資料流動的方向， 如果是按最大的向右流動， 那麼一輪之後， 這一輪最右的那個位置就不在下一輪的範圍內了。
同理， 如果是最大的向左流動， 那麼這一輪最左的位置， 就不在下一輪的範圍內了。
### 插入排序
插入排序的基本思想是， 先預想第一個數， 已經排好了， 然後把第二個數插入到第一個數的佇列中。 同理再把第三個數插入到前面兩個陣列成的佇列中， 依次類推。
例子， 我們要從小到大。 過程如下：
```
1 4 5 3 2 // 原始佇列
1 4 5 3 2 // 1 自己是一個佇列
1 4 5 3 2 // 把 4 加入到 1 中， 4 與 1 比較， 滿足， 不用動
1 4 5 3 2 // 把 5 與 1， 4 比較， 滿足， 不用動
1 3 4 5 2 // 把 3 與 1， 4， 5 比較， 3 應該在 4 前面， 插入
1 2 3 4 5 // 把 2 與 1， 3， 4， 5 比較， 2 應該在 3 前面， 插入
```
### 快速排序
快速排序是我們接觸得比較多的一種演算法了， 總的思想就是先隨機找一個數， 再以這個數為標， 把原來的數就可以分成兩部分（大於標的數與不大於標的數）， 然後再對這分出來的這兩部分再做隨機在其中選一個數， 再往下分， 如此下去， 當不可再分時， 排序也就完成了。
快速排序， 最主要的思想就是分而治之
快速排序， 會快， 其實最主要還是分而治之了， 這樣小的那部分數就不用再和大的那部分數去比較， 好的情況下就少了一半的比較量。 當然差的情況下（每一次其中一部分的數量都是0， 這時的 標的數 就是最小，最大的時候）， 其實和冒泡/插入也一樣了， 基本就要和所有的數依次比較。
例子， 我們要從小到大。 過程如下：
```
1 4 5 3 2 // 以 1 為標的數， 把 1 與最右側的 2 比較， 滿足， 不動
1 4 5 3 2 // 把 1 與最右側的 3 比較， 滿足， 不動
1 4 5 3 2 // 把 1 與最右側的 5 比較， 滿足， 不動
1 4 5 3 2 // 把 1 與最右側的 4 比較， 滿足， 不動
1 3 4 5 2 // 這時就以 1 為中間點， 原先的數分成了兩部分， 只是 1 正好是最小的值， 所以這裡就遇到了最差的情況， 有一部分為0
1 3 4 5 2 // 在這裡就屬於開始下一輪了， 比較 3， 4， 5， 2
1 2 4 5 3 // 3 與 2 比較， 不滿足， 交換
1 2 3 5 4 // 3 與 4 比較， 不滿足， 交換
1 2 3 5 4 // 這裡就以為 3 標， 分成了 2 與 5， 4 兩部分， 然後同樣的方式去排序 5， 4 這一部分， 2 這一部分就不用動了， 只有一個數嘛
。。。。
```
### 選擇排序
這個和插入排序有點類， 不過它是每次在未排序的數中選一個最小（或最大的）， 然後新增到已排序的後面就可以了
插入排序是從未排序的數中隨機選一個， 然後插入到前面已排序的數中， 它的排序比較過程是在已排序中進行的
而選擇的排序是在未排序的數中選出最小（或最大）， 直接排在已排序後面就可以了， 它的比較過程是在未排序數中
例子， 我們要從小到大。 過程如下：
```
1 4 5 3 2 // 先選出最小的1， 並把它放在第1位
1 2 4 5 3 // 在第二位往後， 選出 2， 並把它放在第 2 位
1 2 3 4 5 // 在第三位往後中選出最小的 3 ， 並把它放在已排好序佇列後， 也就是第 3 位
。。。
1 2 3 4 5 // 同理可以把 4， 5 排好， 得到最終的已排好的佇列
```
### 歸併排序
這個方法， 我很少用， 它也有點像分而治之， 它會把整體陣列從中間分成兩部分， 然後遞迴在上一步的部分再分成兩部分， 很明顯， 這樣操作之後， 整個陣列就被分成了一顆樹， 然後從樹支開始， 相鄰兩個兄弟結點比較排序， 完成後， 就往上回溯為父結點， 這樣回溯到最終結點， 整個陣列的排序也就完成了。
先把 1 4 5 3 2 做成這樣一棵樹
1 4 5 | 3 2
| |
|───────| |───────|
| | | |
1 4 | 5 | 3 | 2
|
|───────|
1 4 5 3 2
再把樹回溯
1 4 5 3 2
|───────|
|
1 4 | 5 | 3 | 2
|───────|
|
1 4 5 | 2 3
|───────|
|
1 2 3 4 5
所以這個演算法， 其實是要先構建樹， 然後再回溯， 回溯（收縮）時的比較， 只需要兩個兄弟結點各自前面的兩個數， 因為結點本身是已經排好序的了。
### 基數排序
基數排序這個挺有意思的， 總的來說， 就是先以個位數來排序， 然後再以十位數來排序， 依次往大的位數上來排。
在排序的時候， 其實也很有意思， 不是用的我們傳統上的兩兩比較， 而是分組， 按當前比較位數分對應的組就可以了。
例子， 我們要從小到大。 過程如下：
```
32 42 95 89 57 24
32 42 24 95 57 89 // 按個位排序後
24 32 42 57 89 95 // 按十位排序後
// 這裡就完成了排序， 這裡面最大的數就是兩位， 所以只需要排兩輪。
```
其實從上面的例子過程中可以看出來， 基數排序把以前的整數作比較， 變成了只比較對應位數上的值， 或者可以換個說法， 放十個桶（0 - 9） ， 當比較對應位時， 就按位把數放進桶中， 放完再依次合到原陣列中， 再按下一位再放進桶中， 所以其實數位的比較就放在了分組這一部分了。
### 希爾排序
要理解希爾排序， 其實就要了解到簡單的氣泡排序， 在最差情況下（最小的數在最大的數的位置上）， 那最小的數要回到自己的位置要跟所有的數依次比較， 每比一次， 前進一步。 希爾排序就想解決這個問題， 它是這樣做的： 把所有的數按座標以 step 為步進分組（ step 第一次一般為陣列 length/2 ）， 然後就會有 length/2 個小組， 然後在每個小組裡各自排序， 然後將 step 除 2， 這樣就有 length/4 個小組。 在這些小組內再排序。 依次把 step 除2 ， 直到 step 變為1， 整個陣列是一個小組，排序也就完成了。
例子， 我們要從小到大。 過程如下：
```
32 42 95 89 57 24
32 42 24 89 57 95 // step： 3 => 32， 89 | 42， 57 | 95， 24 為組
24 32 42 57 89 95 // step： 1 => 整個組為一個小組
```
希爾排序就是把大組分成小組來排， 然後再慢慢按step分成大組來排。
### 堆排序
堆排序這個一般用二叉樹， 首先用當前的陣列構建一個樹， 然後從第一個非葉結點開始， 保證當前結點大於自己的兩個子結點。 如果不滿足， 就把大於當前結點的子結點與當前結點的數交換， 再依次往上走。 那麼這樣之後， 明顯我們可以知道， 根結點肯定是最大的數， 然後把這個最大的數放在排好的序中最大的位置上。 再把樹中最後位置的數放到根結點中。 再重複做剛才的事。從這個流程可知， 其實就是在用樹來選最大的值， 這個就和選擇排序有點像了， 只是我們在做選擇排序的選擇時， 是一個一個比較去選， 這裡是透過樹來選。
——-
