PHP에서 병합 정렬을 구현하는 방법-PHP 튜토리얼-php.cn

이 글에서는 주로 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에 넣습니다. , move 해당 포인터, 결과는 다음과 같습니다.

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의 뒤쪽에 삽입하고 A 9만 남겨두고 시퀀스 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

전반부와 후반부를 고려하세요. half as 시퀀스가 다시 병합되면(즉, 분할, 정렬 및 병합) 다음과 같습니다.

Before:

4 3
7 9

After:

2 8
6

Similarly again 각 병합에 대해 자체 시퀀스를 다시 정렬합니다(분할, 정렬, 병합).

분할된 하위 시퀀스에 요소(길이 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，因此会浪费一些资源。因此在实际的排序中还是相对的较少使用。

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