​PHP Array—How to use merge sort?

We know so much about arrays in PHP. I don’t know how much you know about merge sorting. I believe that a large number of people don’t know this part of the knowledge. So don’t worry, this article will lead you to a deeper understanding. to understand this content.

Related recommendations: What is the search algorithm in PHP arrays? How to find it?

Merge sort:

Merge sort (ERGE-SOQfT) is an effective sorting algorithm based on the merge operation. The algorithm uses A very typical application of Divide and Conquer. Merge the already ordered subsequences to obtain a completely ordered sequence; that is, first make each subsequence orderly, and then make the subsequence segments orderly. If two ordered lists are merged into one ordered list, it is called a two-way merge. Let’s take the code as an example:

<?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));

The results are as follows:

The merge sort algorithm is:

1 ) splits the array into two arrays. .

2) Repeat step 1 to split the array into the smallest units. .

3) Apply for space so that its size is the sum of the two sorted sequences. This space is used to store the merged sequence.

4) Set two pointers, the initial positions are the starting positions of the two sorted sequences. .

5) Compare the elements pointed to by the two pointers, select the relatively small element and put it into the merge space, and move the pointer to the next position.

6) Repeat step 3 until a pointer exceeds the end of the sequence. .

7) Copy all remaining elements of the other sequence directly to the end of the merged sequence.

The code is as follows:

$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));

Recommended learning: "PHP Video Tutorial"

The above is the detailed content of ​PHP Array—How to use merge sort?. For more information, please follow other related articles on the PHP Chinese website!