排序算法

快速排序

归并排序算法虽好，但是不是原地排序算法，需要消耗额外的内存空间，今天我们要介绍的是常规排序里综合排名最高的排序算法：快速排序，江湖人称「快排」。

快排的核心思想是这样的：

如果要排序数组中下标从 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 大，我们以递归的方式处理该流程，最终整个数组都会变成有序的，对应的算法操作流程如下：

将上述流程转化为 PHP 代码实现如下：