快速排序(Quick Sort)演算法又稱為劃分交換排序(Partition-Exchange Sort)演算法,是實用性很高的排序演算法,它可以在O(nlogn)的時間複雜度完成排序,雖然是不穩定排序,但它的速度完全可以彌補這個缺點。



快速排序法(Quick Sort)

快速排序法的概念

大致上來說,快速排序法就是先在序列中找出一個元素作為支點(pivot),然後想辦法將比支點的元素移動到支點元素的左邊,比支點大的元素移動到支點元素的右邊,接著再用同樣的方法繼續對支點的左邊子陣列和右邊子陣列進行排序。

快速排序法的過程

假設現在有個陣列資料,內容如下:

索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

要如何將它遞增排列呢?

一開始當然要先選擇一個支點。在此就選擇陣列最前端的位置為支點好了,如下表所示:

       ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

接著從最尾端開始,往前尋找比支點元素還要小的元素。可以找到索引8的元素32,比支點元素69還要小。如下表所示:

       ●                              <
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

接著從除了支點的最左端開始,尋找比支點元素還要更大的元素。可以找到索引1的元素81,比支點元素69還要大。如下表所示:

       ●  >                          <
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

若此時比支援元素更大的元素位置小於比支點元素更小的元素位置(換句話說就是,比支點元素更大的元素在比支點元素更小的元素左邊),則交換兩個元素的位置,如下表所示:

       ●  >                          <
索引    0   1   2   3   4   5   6   7   8   9
數值   69  32  30  38   9   2  47  61  81  79
           └─────────────┘

接著從原先比支點元素更小的元素位置繼續向左尋找比支點元素更小的元素。可以找到索引7的元素61,比支點元素69還要小。如下表所示:

       ●  >                      <
索引    0   1   2   3   4   5   6   7   8   9
數值   69  32  30  38   9   2  47  61  81  79

因為索引7還在原先比支點元素更大的元素位置之右邊,因此再繼續從原先比支點元素更大的元素位置,向右尋找比支點元素更大的元素。可以找到索引8的元素81,比支點元素69還要大。如下表所示:

       ●                          <  >
索引    0   1   2   3   4   5   6   7   8   9
數值   69  32  30  38   9   2  47  61  81  79

此時比支點元素更大的元素位置大於比支點元素更小的元素位置(換句話說就是,比支點元素更大的元素在比支點元素更小的元素右邊),則將比支點元素更小的元素與支點元素交換,如下表所示:

       ●                          <  >
索引    0   1   2   3   4   5   6   7   8   9
數值   61  32  30  38   9   2  47  69  81  79
       └─────────────┘

                                   ○
索引    0   1   2   3   4   5   6   7   8   9
數值   61  32  30  38   9   2  47  69  81  79

支點元素被交換了之後,可以發現支點元素被換到的位置,也就是索引7,其左邊的元素正好都小於支點元素,而右邊的元素正好都大於支點元素。

接下來再針對支點元素左邊的子陣列和支點右邊的子陣列進行排序,排序過程如下:

       ●                         | ○
索引    0   1   2   3   4   5   6 |  7   8   9
數值   61  32  30  38   9   2  47 | 69  81  79

       ●                      < | ○
索引    0   1   2   3   4   5   6 |  7   8   9
數值   61  32  30  38   9   2  47 | 69  81  79

       ●                      <  > | ○
索引    0   1   2   3   4   5   6     |  7   8   9
數值   61  32  30  38   9   2  47     | 69  81  79

       ●                      <  > | ○
索引    0   1   2   3   4   5   6     |  7   8   9
數值   47  32  30  38   9   2  61     | 69  81  79
       └───────────┘

                               ○ | ○
索引    0   1   2   3   4   5   6 |  7   8   9
數值   47  32  30  38   9   2  61 | 69  81  79

       ●                     | ○ | ○
索引    0   1   2   3   4   5 |  6 |  7   8   9
數值   47  32  30  38   9   2 | 61 | 69  81  79

       ●                  < | ○ | ○
索引    0   1   2   3   4   5 |  6 |  7   8   9
數值   47  32  30  38   9   2 | 61 | 69  81  79

       ●                  <  > | ○ | ○
索引    0   1   2   3   4   5     |  6 |  7   8   9
數值   47  32  30  38   9   2     | 61 | 69  81  79

       ●                  <  > | ○ | ○
索引    0   1   2   3   4   5     |  6 |  7   8   9
數值    2  32  30  38   9  47     | 61 | 69  81  79
       └─────────┘

                           ○ | ○ | ○
索引    0   1   2   3   4   5 |  6 |  7   8   9
數值    2  32  30  38   9  47 | 61 | 69  81  79

       ●                 | ○ | ○ | ○
索引    0   1   2   3   4 |  5 |  6 |  7   8   9
數值    2  32  30  38   9 | 47 | 61 | 69  81  79

       <                 | ○ | ○ | ○
索引    0   1   2   3   4 |  5 |  6 |  7   8   9
數值    2  32  30  38   9 | 47 | 61 | 69  81  79

       ○                 | ○ | ○ | ○
索引    0   1   2   3   4 |  5 |  6 |  7   8   9
數值    2  32  30  38   9 | 47 | 61 | 69  81  79

       ○ | ●             | ○ | ○ | ○
索引    0 |  1   2   3   4 |  5 |  6 |  7   8   9
數值    2 | 32  30  38   9 | 47 | 61 | 69  81  79

       ○ | ●          < | ○ | ○ | ○
索引    0 |  1   2   3   4 |  5 |  6 |  7   8   9
數值    2 | 32  30  38   9 | 47 | 61 | 69  81  79

       ○ | ●      >  < | ○ | ○ | ○
索引    0 |  1   2   3   4 |  5 |  6 |  7   8   9
數值    2 | 32  30  38   9 | 47 | 61 | 69  81  79

       ○ | ●      >  < | ○ | ○ | ○
索引    0 |  1   2   3   4 |  5 |  6 |  7   8   9
數值    2 | 32  30   9  38 | 47 | 61 | 69  81  79
                    └─┘

       ○ | ●      <  > | ○ | ○ | ○
索引    0 |  1   2   3   4 |  5 |  6 |  7   8   9
數值    2 | 32  30   9  38 | 47 | 61 | 69  81  79

       ○ | ●      <  > | ○ | ○ | ○
索引    0 |  1   2   3   4 |  5 |  6 |  7   8   9
數值    2 |  9  30  32  38 | 47 | 61 | 69  81  79
            └───┘

       ○ |         ○     | ○ | ○ | ○
索引    0 |  1   2   3   4 |  5 |  6 |  7   8   9
數值    2 |  9  30  32  38 | 47 | 61 | 69  81  79

       ○ | ●     | ○     | ○ | ○ | ○
索引    0 |  1   2 |  3   4 |  5 |  6 |  7   8   9
數值    2 |  9  30 | 32  38 | 47 | 61 | 69  81  79

       ○ | <     | ○     | ○ | ○ | ○
索引    0 |  1   2 |  3   4 |  5 |  6 |  7   8   9
數值    2 |  9  30 | 32  38 | 47 | 61 | 69  81  79

       ○ | ○     | ○     | ○ | ○ | ○
索引    0 |  1   2 |  3   4 |  5 |  6 |  7   8   9
數值    2 |  9  30 | 32  38 | 47 | 61 | 69  81  79

       ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○ | ●
索引    0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8   9
數值    2 |  9 | 30 | 32 | 38 | 47 | 61 | 69 | 81  79

       ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○ | ●  <
索引    0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8   9
數值    2 |  9 | 30 | 32 | 38 | 47 | 61 | 69 | 81  79

       ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○ | ●  <  >
索引    0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8   9
數值    2 |  9 | 30 | 32 | 38 | 47 | 61 | 69 | 81  79

       ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○ | ●  <  >
索引    0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8   9
數值    2 |  9 | 30 | 32 | 38 | 47 | 61 | 69 | 79  81
                                               └─┘

       ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○ |     ○
索引    0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8   9
數值    2 |  9 | 30 | 32 | 38 | 47 | 61 | 69 | 79  81

       ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○
索引    0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9
數值    2 |  9 | 30 | 32 | 38 | 47 | 61 | 69 | 79 | 81

quick-sort

快速排序法的程式實作

在實作程式的時候,應該要避免使用遞迴(Recursive)的結構,因為遞迴需要不斷地重新建構函數的堆疊空間,硬體資源的負擔會比較大,且若是遞迴層數過多還會導致堆疊溢出(Stack Overflow)。所以比較好的做法還是在一個函數內以迴圈迭代的方式來完成。

由於快速排序法本身就是一種原地(in-place)演算法的關係,因此也很容易轉換成迭代的結構來實作,只需要多加一個堆疊結構(可以直接用陣列)來模擬函數的堆疊空間即可。至於這個堆疊結構的大小只要大概相等於要排序的序列的長度即可,再怎麼差的情況下堆疊的長度都不會增長到超過要排序的序列的長度。

為了避免遭遇固定的最差案例,支點的選擇不應該每次都用最左邊的索引位置,隨機選擇會比較保險。

實務上使用快速排序法時,常會去檢查子序列的大小是否過長(長度大於7~15),如果子序列長度不長,會使用適合拿來排序少量資料的插入排序等演算法來完成排序。

快速排序法的複雜度

以#{{n}}#來表示要排序的資料筆數。

項目備註
最差時間複雜度#{{O(n^2)}}#選擇到的支點元素剛好都是最大或最小值。
最佳時間複雜度#{{O(n \log n)}}#選擇到的支點元素剛好都是中間值。
平均時間複雜度#{{O(n \log n)}}#
額外最差空間複雜度#{{O(n)}}#可優化成#{{O(\log n)}}#。
是否穩定