PHPでマージソートを実装する方法-PHPチュートリアル-php.cn

PHPでマージソートを実装する方法

墨辰丷

リリース： 2023-03-28 17:38:02

オリジナル

1512 人が閲覧しました

この記事では、主に PHP マージソートの実装アルゴリズム、つまり、ソート対象のシーケンスをいくつかの順序付けされた部分シーケンスに分割し、その後、順序付けられた部分シーケンスを全体の順序付けされたシーケンスにマージするアルゴリズムを紹介します。興味のある友達は来て調べてください。

マージソート方法は、2 つ (またはそれ以上) の順序付きリストを新しい順序付きリストにマージすることです。マージソートの欠点の 1 つは、データ項目の数と同じサイズの別の配列用のメモリが必要になることです。最初の配列がほぼメモリ全体を占有している場合、マージソートは機能しませんが、十分なスペースがある場合は、マージソートが適切な選択肢になる可能性があります。

ソートされるシーケンスを想定します:

4 3 7 9 2 8 6

まず、マージソートの中心となるアイデアについて説明します。ソートされた 2 つのシーケンスを 1 つのソートされたシーケンスにマージすることです。

上記のシーケンスは 2 つのシーケンス:

4 3 7 9
と
2 8 6

に分割でき、その後 2 つのシーケンスは別々にソートされます。結果は次のようになります:

は sequence に設定されますA、シーケンス B で、

3 4 7 9
2 6 8

上記の 2 つのシーケンスをソートされたシーケンスにマージします:

マージの具体的なアイデアは次のとおりです:

2 つの位置を設定するインジケーター、それぞれシーケンス A とシーケンス B の開始位置を指します: 赤はインジケーターが指す位置です:

3 4 7 9
2 6 8

要素の値を比較します2 つのインジケーターによって示され、小さい方がシーケンス C などの新しい配列に挿入され、対応するインジケーターが 1 ビット後方に移動されます。
結果は次のようになります:

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 の後ろに挿入し、A 9 だけを残してシーケンス C に挿入します。
シーケンス C の結果:

2 3 4 5 6 7 8 9

このようにして、2 つの順序付きシーケンスが 1 つの順序付きシーケンスにマージされます。シーケンス操作、

まず、このマージされた 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 はすべての要素の合計です)。

上記の説明を通じて、2 つのソートされた配列を合計するプロセスを実装しました。

この時点で、これがシーケンス全体のマージソートとどのような関係があるのかという疑問があるかもしれません。あるいは、最初の 2 つのソートされたサブシーケンスをどのようにして取得したのでしょうか?

次に、マージソートとは何かを説明し、次に上記のマージとマージソートの関係を見ていきます:

次の配列をソートする必要があるとき、最初にソートできるでしょうか? 考えてみるとよいでしょう。配列の前半と後半をマージして別々に並べ替えてから、並べ替えた結果を結合するとどうなるでしょうか?

例: ソートする配列:

4 3 7 9 2 8 6

まず 2 つの部分に分割します:

4 3 7 9

2 8 6

前半と後半は、シーケンスが再度マージ (つまり、分割、ソート、マージ) されると、次のようになります:

Before:
4 3

7 9

After:
2 8

同様にマージごとに、自己シーケンスを再度ソートします (分割、ソート、マージ)。

分割されたサブシーケンスに要素 (長さ 1) が 1 つだけある場合、シーケンスはそれ以上分割する必要がなく、ソートされた配列になります。次に、このシーケンスを他のシーケンスとマージし、最後にすべてを完全にソートされた配列にマージします。

プログラムの実装:

上記の説明を通じて、このプログラミングを実装するために再帰的プログラムを使用できると考える必要があります:

このプログラムを実装するには、次の問題を解決する必要がある場合があります:

配列の変換方法分割を行います:

2 つのポインターを設定します。1 つは $left であると想定される配列の先頭を指し、もう 1 つは配列 $right の最後の要素を指します:

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，因此会浪费一些资源。因此在实际的排序中还是相对的较少使用。

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