归并排序
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
归并过程
归并排序的核心就是如何将两个有序序列进行合并,假定有两个有序数组,比较两个有序数组的首个元素,谁小就取谁,并将该元素放入第三个数组中,取了之后在相应的数组中将删除此元素,依次类推,当取到一个数组已经没有元素时,就可将另一数组的剩余元素直接添加到第三个数组中。
原理
1、将序列每相邻两个数字进行归并操作,形成ceil(n/2)个序列,排序后每个序列包含两个元素,最后一个序列可能只有一个元素。
2、将上述序列再次归并,形成ceil(n/4)个序列,每个序列包含四个元素,最后一个序列可能只有三个及以下元素。
3、重复步骤2,直到所有元素排序完毕。
举例
对数组[53,89,12,6,98,25,37,92,5]进行排序
第一次归并后
(53,89),12,(6,98),(25,37),(5,92)
第二次归并后
(12,53,(6,92)
第三次归并后
(6,92)
第四次归并后
5,98
PHP代码实现
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持编程之家。