Quick Sort

快速排序（Quick Sort） 是一种采用分治法思想的排序算法，其主要过程大概如下：

1. 挑选基准值：从数列中挑出一个元素，称为“基准”（pivot），
2. 分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成，
3. 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

一个可能的简单的伪码实现如下：

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

但这样的实现意味着我们需要 $O(n)$ 额外的空间开销，所以一般我们会采用一个无需额外空间，使用双指针，原地分割的版本：

 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
 }

 procedure quicksort(a, left, right)
     if right > left
         select a pivot value a[pivotIndex]
         pivotNewIndex := partition(a, left, right, pivotIndex)
         quicksort(a, left, pivotNewIndex-1)
         quicksort(a, pivotNewIndex+1, right)

Tips:

特别需要注意这个 partition 函数，要注意双指针的边界问题，在实际实现的过程中要十分小心。不然很容易死循环或者越界。

和归并排序不同，快速排序本身是个不稳定排序，其时间复杂度受到数组本身和 pivot 选取的影响，其时间复杂度可以总结为下：

复杂度
平均时间复杂度	$O(n\log n)$
最坏时间复杂度	$O(n^2)$
最优时间复杂度	$O(n\log n)$

由于时间复杂度受到 pivot 选取的影响，我们可以考虑对选取过程进行优化。

第一种是使用随机数来选取 pivot，随机化快速排序可以对于绝大多数输入数据达到 $O(n\log n）$ 的期望时间复杂度。

第二种是三数取中，假设数组被排序的范围为 left 和 right，center=（left+right/2，对a[left]、a[right] 和 a[center] 进行适当排序，取中值为中轴，将最小者放 a[left] ，最大者放在 a[right]，把中轴元与 a[right-1] 交换，并在分割阶段将i和j初始化为 left+1 和 right-2。然后使用双向便利法，进行快排。

参考：

• 快排优化
• 双向快排