Quick Sort

有一個基準點，從左邊過來要比較小，從右邊過來要比較大 跳位速度比較快，先把資料調到大概的位置 (效率最差的時候就是進來的資料已經是排序好的)

• R1 ~ R10 代表在 array 的位置
• left、right 代表現在要 sort 的範圍
• 一開始把 R1 的資料做為基準，把所有資料 scan 一次，比 R1 還小的放左邊，比 R1 大的放右邊

1. 把 R1 的資料 26 做為基準
2. → 從左邊看過來 R2 < R1，OK
3. → R3 > R1，紀錄一下等下要做交換
4. ← 從右邊看過來 R10，R10 < R1，但事實上從右邊看過來應該要比 R1 大，所以這筆資料要拿來交換
5. 將 R3 和 R10 的資料交換
6. → 接下來從左邊開始看到 R4 < R1，OK
7. → R5 > R1，要記錄下來等下做交換
8. ← 再從右邊看 R9 > R1，OK
9. ← R8 < R1，不對
10. 將 R8 和 R5 的資料交換
11. → 接下來 R6 < R1，OK
12. → 接下來 R7 > R1，從左邊過來但比較大，有問題，記錄下來等下做交換
13. ← 從右邊看過來 R7 > R1，從右邊過來比較大，OK
14. ← 接下來 R6 < R1，從右邊看過來是有問題
15. 交叉了，代表所有資料都看過了
16. 接下來把 R1 放在交叉的位置，及 R1 和 R6 交換
17. 接下來將 R6 的左邊和右邊各自做 recursive，以此類推

性質

1. 方法 : 以每組的第一個資料為基準(pivot)，把比它小的資料放在左邊，比它大的資料放在右邊，之後以 pivot 中心，將這組資料分成兩部份。然後兩部分資料各自 recursively 執行相同方法。
2. 平均而言，Quick Sort 有很好效能
3. 效率最差的時候就是進來的資料已經是排序好的
4. 時間複雜度

演算法

從左邊過來叫 i，右邊過來叫 j