第五章：PHP编程思想提升篇——快速排序
更新于：2017-04-23 21:51:23
快速排序是 C.R.A.Hoare 于 1962 年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。快速排序被称为 20 世界十大算法之一。
快速排序和冒泡排序类似，不断的通过比较和移动交换来实现排序，只不过它的实现增大了比较和移动的距离，把较大的数据移动到后面，较小的数据移动到前面，从而减少了总的比较和移动交换次数。快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序其实是非常好理解，比希尔排序代码简单，一个for循环就可以。但是要用到递归，所以如果数列比较大，会消耗内存资源的。
思路：
1、把一个数列第一个数当成一个基数，如图中“49”，然后把比“49”小的数放在左边，比“49”大的数放在右边。看图中第2行。
2、“49”两边的数列又可以分别当成独立的数列，重复执行以上动作（使用递归），直到数组不能再分解，就能得到答案。
代码很简单：
上面的快速排序是一个简单版本的，把“基数”两边的数当成新的数组使用递归重新来一次快速排序。它每次都是把两边的数单独拿出来（就是又重新向内存申请了空间），而不是在原数组上排序，所以占用的内存会逐步增多。
做个测试：
在代码中使用memory_get_usage()函数，可以查看程序在运行中占用内存的情况。
做一个200000个数的快速排序，一开始占用内存：
最高峰时是：
59234240 - 27854408 = 31379832（byte）= 29M
PHP脚本程序在处理快速排序这块代码时向内存多申请了29M内存。
下面我们做下改进，递归时尽量在原数组上做排序。主题思想还是原来的思想，只是代码会有很大变动，做下图解：
1、上面是一个数组，进行快速排序，我们还是把第一个数“6”当做基数，在代码中需要设置两个指针变量“$left”和“$right”，每次排序前“$left”指着数组的第一个位置，“$right”指着数组的最后一个位置。
2、“$right”指针向自右向左移动，什么时候停止呢？找到小于或等于基数的时候停止，然后把“$left”指向的数替换掉。看下图：
3、“$left”紧接着自左向右移动一位。
4、“$left”指针向自左向右移动，什么时候停止呢？找到大于或等于基数的时候停止，然后把“$right”指向的数替换掉。看上图：“$right”指向的数是“3”，“3”在第2步中，已从下标“3”移到下标“0”的位置上。
5、“$right”紧接着自右向左移动一位。
6、当“$left”和“$right”同时指向一个地方时，就可以把基数放到两个指针变量都指向的地方。
7、利用递归把“6”两边的数组再做一次快速排序，直到数组不能再分解为止，就能得到最后的答案。
上代码：
我们来看下改进版的快速排序内存使用情况：
最高峰时：
基本上是没有多大变化。减少了对内存的占用，对效率上来说也会有很大提高，大家可以用microtime(true)做下测试。