快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），最早由图灵奖得主 东尼·霍尔提出。在平均状况下，排序 n 个项目要 O(nlogn)（大O符号）次比较。在最坏状况下则需要 O(n^2) 次比较，但这种状况并不常见。事实上，快速排序 Θ(nlogn) 通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成。

“快速排序”的思想很简单使用分治法（divide and conquer）来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列，整个排序过程只需要三步：

  1. 挑选基准值: 在数据集之中，选择一个元素作为”基准”（pivot）。
  2. 分割: 所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。(与基准值相等的数可以放到任何一边)
  3. 递归排序子序列: 对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个或零个元素为止。

递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。

选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。

示例

现在有一个数据集 {85, 24, 63, 45, 17, 31, 96, 50}，怎么对其排序呢？

第一步，选择中间的元素 45 作为 基准。（基准值可以任意选择，但是选择中间的值比较容易理解。）

1
2

          ↓
85 24 63  45  17 31 96 50

第二步，按照顺序，将每个元素与 基准 进行比较，形成两个子集，一个”小于45”，另一个”大于等于45”。

1
2

              ↓
| 24 17 31 | 45 | 85 63 96 50 |

第三步，对两个子集不断重复第一步和第二步，直到所有子集只剩下一个或零个元素为止。

1
2

     ↓                ↓
| 24 17 31 | 45 | 85 63 96 50 |

45 的左子集 {24, 17, 31} 排序后所有的节点都大于 17,因此 17 的左子集为空

1
2

   ↓                     ↓
| 17 | 24 31 | 45 | 50 | 63 | 85 96 |

1
2

        ↓                     ↓
| 17 | 24 31 | 45 | 50 | 63 | 85 96 |

1

| 17 | 24 | 31 | 45 | 50 | 63 | 85 | 96 |

实现

在简单的伪代码中，此算法可以被表示为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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))
     }
 }

原地（in-place）分割的版本

上面简单版本的缺点是，它需要 Ω(n) 的额外存储空间，也就跟 归并排序 一样不好。额外需要的存储器空间配置，在实际上的实现，也会极度影响速度和缓存的性能。有一个比较复杂使用原地（in-place）分割算法的版本，且在好的基准选择上，平均可以达到 O(logn) 空间的使用复杂度。

示例如下:

1
2

      ↓         ↓  // 将 基准值换到末尾
3 7 8 5 2 1 9 5 4

从最左侧开始将小于基准值 5 的依次放到左侧, 3<5 放到 index=0 的位置，下一个存储位置 index=1，7、8 大于基准值 5 不变， 4<5，与index=1 的值 7 交换位置

1
2
3
4
5
6
7
8
9
10
11
12

  ↓   ↓            
3 7 8 4 2 1 9 5 5 
    ↓   ↓         // 同理交换 2 与index=2的8交换
3 4 8 7 2 1 9 5 5 
      ↓   ↓       
3 4 2 7 8 1 9 5 5 
        ↓     ↓         
3 4 2 1 8 7 9 5 5 
          ↓     ↓         
3 4 2 1 5 7 9 8 5 
                 
3 4 2 1 5 5 9 8 7 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

 function partition(a, left, right, pivotIndex)
 {
     pivotValue := a[pivotIndex]
     swap(a[pivotIndex], a[right]) // 把pivot移到結尾
     storeIndex := left
     for i from left to right-1
     {
         if a[i] < pivotValue
          {
             swap(a[storeIndex], a[i])
             storeIndex := storeIndex + 1
          }
     }
     swap(a[right], a[storeIndex]) // 把pivot移到它最後的地方
     return storeIndex
 }

这是原地分割算法，它分割了标示为”左边（left）”和”右边（right）”的序列部分，借由移动小于 a[pivotIndex] 的所有元素到子序列的开头，留下所有大于或等于的元素接在他们后面。在这个过程它也为基准元素找寻最后摆放的位置，也就是它回传的值。它暂时地把基准元素移到子序列的结尾，而不会被前述方式影响到。由于算法只使用交换，因此最后的数列与原先的数列拥有一样的元素。要注意的是，一个元素在到达它的最后位置前，可能会被交换很多次。

优化的排序算法

快速排序是二叉查找树（二叉搜索树）的一个空间最优化版本。不是循序地把数据项插入到一个明确的树中，而是由快速排序组织这些数据项到一个由递归调用所隐含的树中。这两个算法完全地产生相同的比较次数，但是顺序不同。对于排序算法的稳定性指标，原地分割版本的快速排序算法是不稳定的。其他变种是可以通过牺牲性能和空间来维护稳定性的。

快速排序的最直接竞争者是堆排序（Heapsort）。堆排序通常比快速排序稍微慢，但是最坏情况的运行时间总是 O(nlongn)。快速排序是经常比较快，除了introsort变化版本外，仍然有最坏情况性能的机会。如果事先知道堆排序将会是需要使用的，那么直接地使用堆排序比等待introsort再切换到它还要快。堆排序也拥有重要的特点，仅使用固定额外的空间（堆排序是原地排序），而即使是最佳的快速排序变化版本也需要 Θ(nlogn) 的空间。然而，堆排序需要有效率的随机存取才能变成可行。

快速排序也与归并排序（Mergesort）竞争，这是另外一种递归排序算法，但有坏情况 Θ(nlogn) 运行时间的优势。不像快速排序或堆排序，归并排序是一个稳定排序，且可以轻易地被采用在链表（linked list）和存储在慢速访问媒体上像是磁盘存储或网络连接存储的非常巨大数列。尽管快速排序可以被重新改写使用在链串列上，但是它通常会因为无法随机存取而导致差的基准选择。归并排序的主要缺点，是在最佳情况下需要 Ω(n) 额外的空间。

总结

快速排序是一种交换类的排序，它同样是分治法的经典体现。在一趟排序中将待排序的序列分割成两组，其中一部分记录的关键字均小于另一部分。然后分别对这两组继续进行排序，以使整个序列有序。在分割的过程中，枢纽值的选择至关重要，本文采取了三位取中法，可以很大程度上避免分组”一边倒”的情况。快速排序平均时间复杂度也为 O(nlogn) 级。

参考文献