第五章：PHP编程思想提升篇——归并排序
更新于：2017-04-24 18:56:37
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
基本思想：
基本思路就是将数组分成二组 A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？
可以将 A，B 组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。
整体思路：
一个数列，先不排序，先递归（分解），分解到每组只有一个数据的时候，按照大小排序合并。
归并排序只做两件事：
（1）“分解”——将序列每次折半划分。
（2）“合并”——将划分后的序列段两两合并后排序。
上代码：
它是在原数组上进行归并排序，所以会省内存空间。上面的代码可能不好理解，再来一段简单的代码：
是不是简洁好多？里面用了几个操作数组的函数（自己查手册），立马就简洁多了。这种写法它会随着排序数字的增多占用的内存空间变大。
六大排序总结：
做下测试，看看这六大排序算法占用的时间：
先做一个20000个数的排序，运行结果：
后三种排序方法远远甩掉前三种排序方法，冒泡排序是最慢的，所以冒泡排序不适合做大量数字排序。
只做后三种排序方法比较，把数字增加到500000个，看结果：
所以快速排序果然名不虚传，是最快速的。
我们在实际应用中是不是就选择“快速排序”？——非也！
在PHP应用中很少有对大量数字排序的需求，楠神让大家学习六种排序方法主要还是拓展大家的编程思想，了解一些排序算法到底是怎么回事。
其实根本用不着我们自己写排序算法，PHP早就内置了很多排序的函数（看手册）。
我们看下内置排序函数的效率：
因为内置函数是用C语言写的，比最快的快速排序效率提高了五六倍。
排序算法当然不止这六个，还有很多，感兴趣的可以多去网上搜索了解。