Rumah >pembangunan bahagian belakang >masalah PHP >​PHP数组—归并排序如何运用?

​PHP数组—归并排序如何运用?

慕斯
慕斯asal
2021-06-24 16:28:121254semak imbas

PHP中我们了解了那么多关于数组的知识,不知道你们对归并排序有多少了解,我相信很大一部分人会不知道这部分知识点,那么不急本篇文章就是带领大家更深刻的去了解这个内容。

相关推荐:PHP数组中什么是查找算法?如何查找?

归并排序:

归并排序(ERGE-SOQfT)是建立在归并操作,上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成-一个有序表,称为二路归并。我们以代码为例:

<?php
//PHP数组排序算法:合并算法.
//二路归并
$arr1 = array(1,3,5);
$arr2 = array(2,4,6);
//取出一个空数组用于归并空间
$arr3 = array();
while(count($arr1) & count($arr2)){
//只要$arr1和$arr2里面还有元素,就进行循环
//取出每个数组的第-一个元素:进行比较
$arr3[] = $arr1[0] < $arr2[0] ? array_shift($arr1) : array_shift($arr2);
}
//合并结果
print_r(array_merge($arr3 ,$arr1,$arr2));

结果如下:

1.JPG

归并排序的算法是:

1)将数组拆分成两个数组。 。

2)重复步骤1将数组拆分成最小单元。。

3)申请空间, 使其大小为两个已经排序序列之和,该空间用来存放合并后的序列。

4)设定两个指针, 最初位置分别为两个已经排序序列的起始位置。。

5)比较两个指针所指向的元素, 选择相对小的元素放入到合并空间,并移动指针到下一位置。

6)重复步骤3直到某-指针超出序列尾。。

7)将另-序列剩下的所有元素直接复制到合并序列尾。

代码如下:

$arr = array(4,7,2,1,5,9,3);
//归并排序函数
function merge_sort($arr){
//递归出口
$len = count($arr);
if($len <= 1) return $arr;
//拆分.
$middle = floor($len / 2);
$left = array_slice($arr,0, $middle);
$right = array_slice($arr, $midd1e);
//假设左边和右边都已经排好序:二路归并
$m = array();
while(count($left) && count($right)){
//只要$arr1和$arr2里面还有元素,就进行循环
//取出每个数组的第一个元素: 进行比较
$arr3[] = $left[0] < $right[0] ? array_shift($left) : array_shift($right);
}
//返回结果
return array_merge($m, $left ,$right);
}
print_r(merge_sort($arr));

2.JPG

推荐学习:《PHP视频教程

Atas ialah kandungan terperinci ​PHP数组—归并排序如何运用?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan:
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn