快速排序（QuickSort） 作为最流行的排序算法之一，又有非常出色的性能，被广大的编程语言作为标准库默认排序方法。

快速排序的设计思想是一个很好的分治法（divide-and-conquer） 的实例，理解他的实现原理将有助于我们在实际生产过程中设计自己的解决问题的算法。最直接的，很多算法题目需要使用到类似的思想。

先贴代码（Go）:

func quickSort(nums []int, l, r int) { //[l,r]
   if l < r {
      m := partition(nums, l, r)
      quickSort(nums, l, m-1)
      quickSort(nums, m+1, r)
   }
}

func partition(nums []int, l int, r int) int {
   key := nums[r]
   //all in [l,i) < key
   //all in [i,j] > key
   i := l
   j := l
   for j < r {
      if nums[j] < key {
         nums[i], nums[j] = nums[j], nums[i]
         i++
      }
      j++
   }
   nums[i], nums[r] = nums[r], nums[i]
   return i
}

首先我们先大致介绍一下分治法。很多有用的算法在结构是递归的，为了解决给定的问题，他们多次递归的调用自己去解决一个相关的子问题。这些算法通常遵循分治法，即他们将原问题划分为多个规模更小且与原问题相似的子问题，然后递归的解决子问题，最后合并子问题的答案得到原问题的答案。

分治法在每一次递归阶段都分为三个步骤：

  • 划分： 将问题划分为一系列规模更小的相似子问题。
  • 处理： 递归的解决子问题，如果子问题的规模足够的小，则直接解决它。
  • 合并： 将各个子问题的答案合并为原文题的答案。
    其中在处理过程中，如果子问题规模大到需要递归处理，则我们称它为递归实例（recursive case），如果子问题规模足够的小，递归“到达了最低点”，则我们称它为基础实例（base case）。有时，除了解决相似问题的较小规模的子问题外，我们还必须解决与原问题不太相同的子问题。我们一般将解决此类子问题作为合并步骤的一部分。
nums[p..r]
nums[l..r]nums[l..m-1]nums[m+1..r]nums[l..m-1]nums[m]nums[m+1..r]nums[m]mnums[l..m-1]nums[m+1..r]nums
nums[l..r]
[l,i)key[l,i)key

处理过程如下：

i,jl[l,i)[l,i)
nums[j]
nums[j]keynums[i]nums[j]ijnums[j]keyj
j == rnums[i]keynums[r]nums[r]keyi

因此，在经过以上的处理后，遵循分治法的三个步骤处理，最终数组是升序的。

O（nlogn）
key