共计 1651 个字符，预计需要花费 5 分钟才能阅读完成。
疾速排序（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]。计算索引m的值是此划分过程的一部分。 - 解决： 递归调用疾速排序算法，排序两个子数组
nums[l..m-1]和nums[m+1..r]。 - 合并： 因为子数组曾经排序，所以不须要将它们合并起来，整个数组
nums当初已排好序。
咱们能够发现，算法最外围的局部是 划分 阶段，咱们再次应用 循环不变量 的概念来帮忙咱们思考。咱们设置的 循环不变量 如下：
在待划分的数组 nums[l..r] 中，保护三个范畴状态。
- 数组
[l,i)范畴的所有元素小于key - 数组
[l,i)范畴的所有元素大于等于key
处理过程如下：
初始： i,j都为 l，则数组范畴[l,i) 和[l,i)均无元素，不变量成立。
放弃： 在迭代过程中，依照 nums[j] 的值分为两种解决状况：
- 若
nums[j]小于key，替换nums[i]和nums[j]，同时i后移，j后移，不变量成立。 - 若
nums[j]大于等于key，j后移，不变量成立。
终止： 当 j == r 时，循环终止。此时不变量成立。之后替换 nums[i]（以后数组地位中第一个大于等于 key 的值）和 nums[r]，使得原 nums[r] 的值 key 放入正确地位。同时 i 即是正确地位的值的数组索引号。
因而，在通过以上的解决后，遵循分治法的三个步骤解决，最终数组是升序的。
疾速排序是高效的排序办法，均匀工夫复杂度为O（nlogn），且解决阶段不须要额定的存储空间（旧址排序）。
为了保障疾速排序的性能，通常咱们能够减少一个 随机抽样 的处理过程，即随机抉择数组中的一个值作为 key 值，具体原理能够参考《算法导论》。
