Quick Sort

比較快的--排序

之前，曾經說一個~~泡沫排序法吧
但是，那種速度並不算快。
前幾天，我聽說有個-->目前最佳的排序法
快速排序法(Quick Sort)
來看看他跑的方式吧!

舉例說明比較簡單:
e.g.  有一陣列→  4 , 5 , 6 , 1 , 2 , 3

首先，先找一個鍵值作為分割標準，通常會選第一個作為這個標準
，再來把這個數列分成兩部份，一為比標準大的，另一個則是比標
準小或相等的。

接著，把分過的兩部份在分別執行上述步驟，直到完全排好為止 。
這裡用到的是遞迴的概念。
很難想像  吧 !
ok的，用個例子就能比較清楚了。

請自行對照上面的敘述
如此這般，就變成了
1.選取4為分割標準
→    4 , 5 , 6 , 1 , 2 , 3        /*藍色的為分割標準*/

2.小的站左邊   大的站右邊

(1)這時常用兩個指標來幫我們

   ，且要確認left < right

→   4 , 5 , 6 , 1 , 2 , 3

/*紅色稱為left指標，通常取陣列的第二個，即索引值1

; 綠色的稱為right指標，通常取陣列的最後一個*/   

(2)由left往右找，找到一個比標準還大的值 ; 由right往左找，找到一個比標準還小的值， 若left(陣列索引值)<right(陣列索引值)，兩值交換。

→   4 , 3 , 6 , 1 , 2 , 5

/*  left==1  ;  right==5  */

(3)重覆上述部驟，直到left >= right。

→   4 , 3 , 6 , 1 , 2 , 5    /* left==2 ;  right==4*/

→   4 , 3 , 2 , 1 , 6 , 5    /* left==2 ;  right==4*/

→   4 , 3 , 2 , 1 , 6 , 5   /* left==4 ;  right==3*/

→   4 , 3 , 2 , 1 , 6 , 5    /* left >= right ，跳出迴圈*/

(4)將標準與right交換。

→   1 , 3 , 2 , 4 , 6 , 5   

這樣就完成了一次遞迴，接著將標準的左半和右半分別進行遞迴，這樣就是一個完整的Quick  Sort了。

左半: 1 , 3 , 2

→    1 , 3 , 2

→    1 , 3 , 2       /*right因為找不比標準還小的值，因此一直往左跑，跑到left >= right ，跳出迴圈*/
 然後進行下一次遞迴

→   3 , 2         /*3同時是left指標和right指標， left = right ，跳出迴圈*/
標準與right進行交換
→   2 , 3

右半: 6 , 5

→    6 , 5         

/*此時，5同時是left和right(一開始，left的值=索引值1的值，right的值=陣列最後一項的值) ， left  >= right，因此跳出迴圈，*/

→   5 , 6     /*標準與right進行交換*/

最後結果→   1 , 2 , 3 , 4 , 5 , 6