排序算法值归并排序
1、描述
归并排序实际上是将一个数组分成不能再分为止,然后两两对比,将小的放在前面,然后按照从小到达的分裂顺序,往上走,最后合并两个数组即可。
2、图解
<?php 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); } //归并排序主函数 function MergeSort($arr){ $len=count($arr); if($len <= 1) return $arr;//递归结束条件,到达这步的时候,数组就只剩下一个元素了,也就是分离了数组 $mid = intval($len/2);//取数组中间 $left_arr = array_slice($arr, 0, $mid);//拆分数组0-mid这部分给左边left_arr $right_arr = array_slice($arr, $mid);//拆分数组mid-末尾这部分给右边right_arr $left_arr = MergeSort($left_arr);//左边拆分完后开始递归合并往上走 $right_arr = MergeSort($right_arr);//右边拆分完毕开始递归往上走 $arr=merge($left_arr, $right_arr);//合并两个数组,继续递归 return $arr; } $arr = [4,6,3,0,1,2,7,9,8,5]; $data = MergeSort($arr); var_dump($data);
注意:
1、两个数组比较最后肯定剩下元素,不是A就是B,这是要把数组里面剩的追加到临时数组的后面。
排序类别 | 排序方法 | 时间复杂度 | 空间复杂度 | 稳定性 | ||
平均情况 | 最坏情况 | 最好情况 | ||||
归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |