PHP 병합 sort_php 예제 구현에 대한 자세한 설명

병합 정렬 방법은 두 개 이상의 정렬된 목록을 새로운 정렬된 목록으로 병합하는 것입니다. 병합 정렬의 한 가지 단점은 데이터 항목 수와 동일한 크기의 다른 배열에 대한 메모리가 필요하다는 것입니다. 초기 배열이 메모리 전체를 거의 차지하면 병합 정렬이 작동하지 않지만, 공간이 충분하다면 병합 정렬을 선택하는 것이 좋습니다.

정렬할 순서를 가정합니다.

4 3 7 9 2 8 6

먼저 아이디어에 대해 이야기해 보겠습니다. 병합 정렬의 핵심 아이디어는 두 개의 정렬된 시퀀스를 하나의 정렬된 시퀀스로 병합하는 것입니다.

위의 순서는 다음과 같이 나눌 수 있습니다.

4 3 7 9
그리고
2 8 6

이 두 시퀀스는 별도로 정렬됩니다. 결과는 다음과 같습니다.

은 시퀀스 A, 시퀀스 B로 설정되고,

3 4 7 9
2 6 8

위의 두 시퀀스를 정렬된 시퀀스로 병합합니다.

병합의 구체적인 아이디어는 다음과 같습니다.

각각 시퀀스 A와 시퀀스 B의 시작 위치를 가리키는 두 개의 위치 표시기를 설정합니다. 빨간색은 표시기가 가리키는 위치입니다.

3 4 7 9
2 6 8

두 표시자가 가리키는 요소의 값을 비교하고 더 작은 것을 시퀀스 C와 같은 새 배열에 삽입하고 해당 표시자를 한 위치 뒤로 이동합니다.
결과는 다음과 같습니다.

3 4 7 9
2 6 8

시퀀스 C 형성: 한 요소가 삽입되었고, 더 작은 요소 2가 삽입되었습니다.
2

그런 다음 시퀀스 A와 시퀀스 B의 포인터가 가리키는 요소를 다시 비교합니다. 작은 요소를 시퀀스 C에 넣고 해당 포인터를 이동하면 결과는 다음과 같습니다.

3 4 7 9
2 6 8
2 3

그리고 시퀀스 A 또는 시퀀스 B의 표시기가 배열의 끝으로 이동할 때까지 반복적으로 실행합니다. 예:
여러 번 비교한 후 시퀀스 B는 표시기를 시퀀스의 끝(마지막 요소 뒤)으로 이동했습니다.
3 4 7 9
2 6 8
2 3 4 6 7 8

그런 다음 시퀀스 A의 사용되지 않은 모든 요소를 ​​시퀀스 C에 삽입합니다. 시퀀스 C에는 하나만 남습니다.

시퀀스 C 결과:

2 3 4 5 6 7 8 9

이런 방식으로 두 개의 정렬된 시퀀스를 하나의 정렬된 시퀀스로 병합하는 작업이 실현됩니다.

병합된 PHP 코드를 살펴보겠습니다.

/**
 * 将两个有序数组合并成一个有序数组
 * @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;
}

经过上面的分析和程序的实现，我们不难发现，合并已排序的序列的时间应该是线性的，就是说，最多会发生N-1次比较，其中N是所有元素之和。

通过上面的描述，我们实现了将两个排序好的数组进行和并的过程。

此时，大家可能会有疑问，这个和归并排序整个序列有什么关系？或者你是如何能够得到最开始的两个排序好的子序列的呢？
下面，我们就来描述以下什么是归并排序，然后再看，上面的合并与归并排序的关系是如何的：

大家不妨去想，当我们需要排序如下的数组时，我们是否可以先将数组的前半部分与数组的后半部分分别进行归并排序，然后将排序的结果合并起来呢？

例如：待排序的数组：
4 3 7 9 2 8 6

先分成2部分：

4 3 7 9
2 8 6

将前半部分 与 后半部分 分别看成一个序列，再次进行归并（就是拆分，排序，合并）操作
就会变成：

前：
4 3
7 9

后：
2 8
  6

同样  再对每个自序列进行 归并排序，再次（拆分，排序，合并）。

当拆分的子序列内只存在一个元素（长度为1）时，那么这个序列就不必再拆分了，就是一个排序好的数组了。然后将这个序列，与其他的序列再合并到一起即可，最终就将所有的都合并好了，成为一个完整的排序好的数组。

程序实现：

通过上面的描述 大家应该想到，可以使用递归程序来实现这个程序设计吧：

想要实现这个程序，可能需要解决如下问题：

怎么将数组做拆分：

设定两个指示器，一个指向数组开始假定为$left，一个指向数组最后一个元素$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);

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

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

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

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

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

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