How to implement merge sort in PHP-PHP Tutorial-php.cn

This article mainly introduces the implementation algorithm of PHP merge sort, that is, dividing the sequence to be sorted into several ordered subsequences, and then merging the ordered subsequences into an overall ordered sequence. Interested friends can come and find out.

The merge sorting method is to merge two (or more) ordered lists into a new ordered list. One disadvantage of merge sort is that it requires memory for another array of size equal to the number of data items. If the initial array takes up almost the entire memory, merge sort will not work, but if there is enough space, merge sort can be a good choice.

Assume the sequence to be sorted:

4 3 7 9 2 8 6

Let’s talk about the idea first. The central idea of merging sort is Merge two sorted sequences into one sorted sequence.

The above sequence can be divided into:

4 3 7 9
and
2 8 6

these two sequence, and then sort the two sequences respectively: the result is:

is set to sequence A, and sequence B,

3 4 7 9
2 6 8

Merge the above two sequences into one sorted sequence:

The specific idea of merging is:

Set two Position indicators, pointing to the starting positions of sequence A and sequence B respectively: red is the position pointed by the indicator:

3 4 7 9
2 6 8

Compare the values of the elements pointed to by the two indicators, insert the smaller one into a new array, such as sequence C, and move the corresponding indicator backward at the same time One digit:
The result is:

3 4 7 9
2 6 8

is formed Sequence C: An element has been inserted, the smaller element 2.
2

Then compare again the element pointed to by the indicator in sequence A and sequence B: add the small Put it into sequence C and move the corresponding pointer. The result is:

3 4 7 9
2 6 8
2 3

And so on, iteratively execute until an indicator in sequence A or sequence B has moved to the end of the array. For example:
After multiple comparisons, sequence B has moved the indicator to the end of the sequence (after the last element).
3 4 7 9
2 6 8
2 3 4 6 7 8

Then the unused sequence, which is the rest of sequence A All the elements can be inserted after the sequence C. There is only one 9 left. Insert it after the sequence C:

Result of sequence C:

2 3 4 5 6 7 8 9

In this way, the operation of merging two ordered sequences into one ordered sequence is realized.

Let’s look at this merger first. PHP code:

/**
 * 将两个有序数组合并成一个有序数组
 * @param $arrA,
 * @param $arrB,
 * @reutrn array合并好的数组
 */
function mergeArray($arrA, $arrB) {
  $a_i = $b_i = 0;//设置两个起始位置标记
  $a_len = count($arrA);
  $b_len = count($arrB);
  while($a_i<$a_len && $b_i<$b_len) {
    //当数组A和数组B都没有越界时
    if($arrA[$a_i] < $arrB[$b_i]) {
      $arrC[] = $arrA[$a_i++];
    } else {
      $arrC[] = $arrB[$b_i++];
    }
  }
  //判断 数组A内的元素是否都用完了，没有的话将其全部插入到C数组内：
  while($a_i < $a_len) {
    $arrC[] = $arrA[$a_i++];
  }
  //判断 数组B内的元素是否都用完了，没有的话将其全部插入到C数组内：
  while($b_i < $b_len) {
    $arrC[] = $arrB[$b_i++];
  }
  return $arrC;
}

Copy after login

After the above analysis and program implementation, we can easily find that the time to merge sorted sequences should be linear , that is, at most N-1 comparisons will occur, where N is the sum of all elements.

Through the above description, we have implemented the process of summing two sorted arrays.

At this point, you may have questions, what does this have to do with merging and sorting the entire sequence? Or how did you get the first two sorted subsequences?
Next, we will describe what merge sort is, and then look at the relationship between the above merge and merge sort:

You may wish to think about it, when we need to sort the following array , can we first merge and sort the first half of the array and the second half of the array, and then merge the sorted results?

For example: Array to be sorted:
4 3 7 9 2 8 6

First divide into 2 parts:

4 3 7 9
2 8 6

Consider the first half and the second half as a sequence, and perform the merge (that is, split, sort, merge) operation again
will become Into:

Before:
4 3
7 9

After:
2 8
6

Similarly, merge and sort each self-sequence again (split, sort, merge).

When there is only one element (length 1) in the split subsequence, then the sequence does not need to be split anymore, and it becomes a sorted array. Then merge this sequence with other sequences, and finally merge everything into a complete sorted array.

Program implementation:

Through the above description, you should think that you can use recursive programs to implement this programming:

To implement this program, you may need to solve the following problems:

How to split the array:

Set two indicators, one pointing to the beginning of the array Assuming $left, one points to the last element of the array $right:
4 3 7 9 2 8 6

然后判断 $left 是否小于$right，如果小于，说明这个序列内元素个数大于一个，就将其拆分成两个数组，拆分的方式是生成一个中间的指示器$center，值为$left + $right /2 整除。结果为：3，然后将$left 到$center 分成一组，$center+1到$right分成一组：
4 3 7 9
2 8 6
接下来，递归的利用$left, $center, $center+1, $right分别做为两个序列的左右指示器，进行操作。知道数组内有一个元素$left==$right .然后按照上面的合并数组即可：

/**
* mergeSort 归并排序
* 是开始递归函数的一个驱动函数
* @param &$arr array 待排序的数组
*/
function mergeSort(&$arr) {
  $len = count($arr);//求得数组长度
 
  mSort($arr, 0, $len-1);
}
/**
* 实际实现归并排序的程序
* @param &$arr array 需要排序的数组
* @param $left int 子序列的左下标值
* @param $right int 子序列的右下标值
*/
function mSort(&$arr, $left, $right) {
 
  if($left < $right) {
    //说明子序列内存在多余1个的元素，那么需要拆分，分别排序，合并
    //计算拆分的位置，长度/2 去整
    $center = floor(($left+$right) / 2);
    //递归调用对左边进行再次排序：
    mSort($arr, $left, $center);
    //递归调用对右边进行再次排序
    mSort($arr, $center+1, $right);
    //合并排序结果
    mergeArray($arr, $left, $center, $right);
  }
}
 
/**
* 将两个有序数组合并成一个有序数组
* @param &$arr, 待排序的所有元素
* @param $left, 排序子数组A的开始下标
* @param $center, 排序子数组A与排序子数组B的中间下标，也就是数组A的结束下标
* @param $right, 排序子数组B的结束下标（开始为$center+1)
*/
function mergeArray(&$arr, $left, $center, $right) {
  //设置两个起始位置标记
  $a_i = $left;
  $b_i = $center+1;
  while($a_i<=$center && $b_i<=$right) {
    //当数组A和数组B都没有越界时
    if($arr[$a_i] < $arr[$b_i]) {
      $temp[] = $arr[$a_i++];
    } else {
      $temp[] = $arr[$b_i++];
    }
  }
  //判断 数组A内的元素是否都用完了，没有的话将其全部插入到C数组内：
  while($a_i <= $center) {
    $temp[] = $arr[$a_i++];
  }
  //判断 数组B内的元素是否都用完了，没有的话将其全部插入到C数组内：
  while($b_i <= $right) {
    $temp[] = $arr[$b_i++];
  }
 
  //将$arrC内排序好的部分，写入到$arr内：
  for($i=0, $len=count($temp); $i<$len; $i++) {
    $arr[$left+$i] = $temp[$i];
  }
 
}
 //do some test:
$arr = array(4, 7, 6, 3, 9, 5, 8);
mergeSort($arr);
print_r($arr);

Copy after login

注意上面的代码带排序的数组都使用的是引用传递，为了节约空间。

而且，其中的合并数组的方式也为了节约空间做了相对的修改，把所有的操作都放到了$arr上完成，引用传递节约资源。

好了上面的代码就完成了归并排序，归并排序的时间复杂度为O(N*LogN) 效率还是相当客观的。

再说，归并排序算法，中心思想是将一个复杂问题分解成相似的小问题，再把小问题分解成更小的问题，直到分解到可以马上求解为止，然后将分解得到的结果再合并起来的一种方法。这个思想用个成语形容叫化整为零。放到计算机科学中有个专业属于叫分治策略（分治发）。分就是大问题变小问题，治就是小结果合并成大结果。

分治策略是很多搞笑算法的基础，我们在讨论快速排序时，也会用到分治策略的。

最后简单的说一下这个算法，虽然这个算法在时间复杂度上达到了O(NLogN)。但是还是会有一个小问题，就是在合并两个数组时，如果数组的总元素个数为 N，那么我们需要再开辟一个同样大小的空间来保存合并时的数据（就是mergeArray中的$temp数组），而且还需要将数据有$temp拷贝会$arr，因此会浪费一些资源。因此在实际的排序中还是相对的较少使用。

总结：以上就是本篇文的全部内容，希望能对大家的学习有所帮助。