内容简介：归并排序（英语：Merge sort，或 mergesort），是创建在归并操作上的一种有效的排序算法，效率为
归并排序（英语：Merge sort，或 mergesort），是创建在归并操作上的一种有效的 排序 算法，效率为 O(nlogn) 。1945 年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
采用分治法：
- 分割：递归地把当前序列平均分割成两半。
- 集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。
归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并 排序算法 依赖归并操作。
<?php
function mergeSort($arr)
{
$len = count($arr);
if ($len <= 1) {
return $arr;
} // 递归结束条件, 到达这步的时候, 数组就只剩下一个元素了, 也就是分离了数组
$mid = $len / 2;
$left = array_slice($arr, 0, $mid); // 拆分数组0-mid这部分给左边left
$right = array_slice($arr, $mid); // 拆分数组mid-末尾这部分给右边right
$left = mergeSort($left); // 左边拆分完后开始递归合并往上走
$right = mergeSort($right); // 右边拆分完毕开始递归往上走
$arr = merge($left, $right); // 合并两个数组,继续递归
return $arr;
}
// merge函数将指定的两个有序数组(arrA, arr)合并并且排序
function merge($arrA, $arrB)
{
$arrC = array();
while (count($arrA) && count($arrB)) {
// 这里不断的判断哪个值小, 就将小的值给到arrC, 但是到最后肯定要剩下几个值,
// 不是剩下arrA里面的就是剩下arrB里面的而且这几个有序的值, 肯定比arrC里面所有的值都大所以使用
$arrC[] = $arrA[0] < $arrB[0] ? array_shift($arrA) : array_shift($arrB);
}
return array_merge($arrC, $arrA, $arrB);
}
$startTime = microtime(1);
$arr = range(1, 1000);
shuffle($arr);
echo 'before sort: ', implode(', ', $arr), "\n";
$sortArr = mergeSort($arr);
echo 'after sort: ', implode(', ', $sortArr), "\n";
echo 'use time: ', microtime(1) - $startTime, "s\n";
假设被排序的数列中有 N 个数。遍历一趟的时间复杂度是 O(N) ，需要遍历多少次呢？
归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据 完全二叉树 的可以得出它的时间复杂度是 O(N*lgN) 。
References:
– EOF –
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
