Day 10：快速排序(quicksort)

看完了分治法与递回，再来看这样的方法如何解决排序问题。

快速排序是一种利用分治法的演算法，比前面提到的排序方法都要快速许多，有些程序语言的函式库也直接包含了快速排序的函式，可以直接在实务中运用。

快速排序的步骤是：

1. 在一个数列中挑选出一个数字当作基准(pivot)。
2. 将所有比基准小的元素放前面，所有比基准大的元素放後面。
3. 用递回的方式，对基准两边的数列进行快速排序。

以实际例子来说，如果有一个数列 24, 32, 5, 45, 15, 7，第一步我们随意挑选第一个数字24作为基准。

接下来第二个步骤叫做分割(partitioning)，将比24小的数字放前面，比24大的放後面：

5, 15, 7, 24, 32, 45

经过分割，我们会得到：比基准小的子数列(5, 15, 7)、基准(24)、比基准大的子数列(32, 45)。

接着递回地对子数列进行上述步骤。那麽既然是递回，这里的基本情况是什麽？什麽时候问题会小到排序可以直接完成、不必再分割下去？答案就是当子数列只有0个或1个数字，可以直接当作排序完成。

所以我们将上述例子的子数列(5, 15, 7)、(32, 45)再进行挑选基准和分割，此时得到的子数列长度都<=1，递回结束，最後所有的数列合并可以得到排序好的数列：5, 7, 15, 24, 32, 45。

这样的演算法以虚拟码可以表示为：

source:维基百科

function quicksort(q)
 {
     var list less, pivotList, greater
     if length(q) ≤ 1 
         return q
     else 
     {
         select a pivot value pivot from q
         for each x in q except the pivot element
         {
             if x < pivot then add x to less
             if x ≥ pivot then add x to greater
         }
         add pivot to pivotList
         return concatenate(quicksort(less), pivotList, quicksort(greater))
     }
 }

执行时间

快速排序跟其他演算法比较不一样的地方在於，它的执行时间跟如何挑选基准有很大的关系。

我们可以先想像，无论怎麽挑选基准，每一层递回都会处理阵列里的所有元素，所以每次增加执行堆叠都会经过n次操作，这部份时间为O(n)。换句话说，执行堆叠越少，则整体执行时间越短。

基於上述所说，最坏的情况就是执行堆叠最高的情况。如果每次的基准都是阵列中最大或最小的数字，分割时就会所有元素都被分在同一边，等於每次的子阵列只比原本少一个元素，那麽需要n-1层的递回才能完成排序。再乘以每层的操作时间，整个演算法的最坏情况执行时间为O(n²)。

最佳的情况，则是每次的基准都将阵列分割成两个差不多大小的子阵列，这样就只需要log n层递回。整体执行时间可以缩短为O(n log n)。

以阵列[1, 2, 3, 4, 5, 6, 7, 8]为例，如果以第一个数字作为基准，分割後会得到空阵列[]、[1]、[2, 3, 4, 5, 6, 7]，以此类推，要经过7层递回才能达到基本情况。但如果以4为基准，只要3层次的递回就可以达到基本情况。

不过快速排序的一大优势在於，它的最佳情况执行时间也就是平均情况执行时间，也就是说一般情况下，若随机选择一个元素作为基准，快速排序的平均执行时间即可以达到O(n log n)。