前天给大家分享了归并排序，但是它不是原地排序算法，需要消耗额外的内存空间，今天给大家分享的是江湖无人不知无人不晓的"快排"--快速排序。

快排是小生接触开发学会的第一个排序算法

快速排序原理

快排也用到了分治思想。快排的核心思想是：如果要排序的数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为分区点 pivot 。

我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot ,后面的 q+1 到 r 之间都是大于 pivot 的。

如下图：

根据分治、递归的处理思想，我们可以用递归排序从下标 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据，直到区间缩小为1，就说明所有的数据都有序了。快排不需要归并那样做合并，也不需要额外的存储空间，在时间复杂度一样的情况下有着比归并更好的空间复杂度表现。

快排首先找到分区点，一般我们会将数组第一个或最后一个元素作为 pivot ，我们以最后一个作为分区点 pivot ，然后通过两个变量 i 和 j 作为下标来循环数组，当下标 j 对应数据小于 pivot 时，交换 i 和 j 对应数据，并且将 i 往前移动一位，否则 i 不动，下标 j 始终是往前移动的， j 到达终点后，将 pivot 如下标 i 对应数据交换，这样最终将 pivot 置于数组中间， [0...i-1] 区间的数据都比 pivot 小， [i+1...j] 之间的数据都比 pivot 大，我们以递归的方式循环处理，最终整个数组都会变成有序的，如下图：

因为分区的过程涉及交换操作，如果数组中有两个相同的元素，比如序列 7， 9，5，7，3，6 经过第一次分区操作之后，两个 7的相对先后顺序会改变。所以，快速排序并不是一个稳定的排序算法。

代码示例

Go语言：

PHP示例：

JS示例：

性能分析

最后我们看下快速排序的性能和稳定性：