So implementieren Sie die Zusammenführungssortierung in PHP-PHP-Tutorial-php.cn

In diesem Artikel wird hauptsächlich der Implementierungsalgorithmus der PHP-Merge-Sortierung vorgestellt, dh die Aufteilung der zu sortierenden Sequenz in mehrere geordnete Teilsequenzen und das anschließende Zusammenführen der geordneten Teilsequenzen zu einer geordneten Gesamtsequenz. Interessierte Freunde können vorbeikommen und sich informieren.

Bei der Sortiermethode „Zusammenführen“ werden zwei (oder mehr) geordnete Listen zu einer neuen geordneten Liste zusammengeführt. Ein Nachteil der Zusammenführungssortierung besteht darin, dass sie Speicher für ein weiteres Array benötigt, dessen Größe der Anzahl der Datenelemente entspricht. Wenn das anfängliche Array fast den gesamten Speicher einnimmt, funktioniert die Zusammenführungssortierung nicht. Wenn jedoch genügend Speicherplatz vorhanden ist, kann die Zusammenführungssortierung eine gute Wahl sein.

Nehmen Sie die Reihenfolge an, die sortiert werden soll:

4 3 7 9 2 8 6

Lassen Sie mich zuerst über die Idee sprechen Die zentrale Idee der Zusammenführungssortierung besteht darin, zwei sortierte Sequenzen zu einer sortierten Sequenz zusammenzuführen.

Die obige Sequenz kann unterteilt werden in:

4 3 7 9
und
2 8 6

diese zwei Sequenzen und sortieren Sie dann die beiden Sequenzen separat: Das Ergebnis ist:

wird auf Sequenz A und Sequenz B eingestellt,

3 4 7 9
2 6 8

Fügen Sie die beiden oben genannten Sequenzen zu einer sortierten Sequenz zusammen:

Die spezifische Idee des Zusammenführens ist:

Setzen Sie zwei Positionsindikatoren, die jeweils auf die Startpositionen von Sequenz A und Sequenz B zeigen: Rot ist die Position, auf die der Indikator zeigt:

3 4 7 9
2 6 8

Vergleichen Sie die Werte der Elemente, auf die die beiden Indikatoren zeigen, fügen Sie das kleinere in ein neues Array ein, z. B. Sequenz C, und verschieben Sie es entsprechender Indikator gleichzeitig rückwärts Ein Bit:
Das Ergebnis ist:

3 4 7 9
2 6 8

gebildete Sequenz C: Ein Element wurde eingefügt.
2

wird dann erneut mit dem Element verglichen, auf das der Indikator in Sequenz A zeigt und Sequenz B: Das kleine Setze es in Sequenz C ein und bewege den entsprechenden Zeiger. Das Ergebnis ist:

3 4 7 9
2 6 8
2 3

Und so weiter, iterativ ausführen, bis sich ein Indikator in Sequenz A oder Sequenz B an das Ende des Arrays bewegt hat. Beispiel:
Nach mehreren Vergleichen hat Sequenz B den Indikator an das Ende der Sequenz (nach dem letzten Element) verschoben.
3 4 7 9
2 6 8
2 3 4 6 7 8

Dann gibt es ungenutzte Sequenzen, die den Rest von Sequenz A darstellen Elemente können nach der Sequenz C eingefügt werden. Es gibt nur noch eine 9, die nach der Sequenz C übrig bleibt:

Ergebnis der Sequenz C:

2 3 4 5 6 7 8 9

Auf diese Weise wird der Vorgang des Zusammenführens zweier geordneter Sequenzen zu einer geordneten Sequenz realisiert

Schauen wir uns zuerst diesen PHP-Code an:

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

Nach dem Login kopieren

Nach der obigen Analyse und Programmimplementierung ist es nicht schwer herauszufinden, dass die Zeit zum Zusammenführen sortierter Sequenzen linear sein sollte, das heißt bei Die meisten N-1-Vergleiche werden durchgeführt, wobei N die Summe aller Elemente ist.

Durch die obige Beschreibung haben wir den Prozess der Summierung zweier sortierter Arrays implementiert.

An dieser Stelle haben Sie möglicherweise Fragen: Was hat das mit der gesamten Reihenfolge der Zusammenführungssortierung zu tun? Oder wie bekommt man die ersten beiden sortierten Teilsequenzen?
Als nächstes beschreiben wir, was Zusammenführungssortierung ist, und schauen uns dann die Beziehung zwischen der oben genannten Zusammenführung und Zusammenführungssortierung an:

Sie können genauso gut darüber nachdenken, wenn wir das folgende Array sortieren müssen. Können wir zuerst die erste Hälfte des Arrays und die zweite Hälfte des Arrays zusammenführen und sortieren und dann die sortierten Ergebnisse zusammenführen?

Zum Beispiel: Zu sortierendes Array:
4 3 7 9 2 8 6

Zuerst in 2 Teile teilen:

4 3 7 9
2 8 6

Betrachten Sie die erste Hälfte und die zweite Hälfte als Sequenz und führen Sie den Zusammenführungsvorgang (d. h. Teilen, Sortieren, Zusammenführen) erneut aus
wird zu:

Vorderseite:
4 3
7 9

Rückseite:
2 8
6

Führen Sie auf ähnliche Weise jede Selbstsequenz erneut zusammen und sortieren Sie sie (teilen, sortieren, zusammenführen).

Wenn die geteilte Teilsequenz nur ein Element (Länge 1) enthält, muss die Sequenz nicht mehr geteilt werden und wird zu einem sortierten Array. Führen Sie diese Sequenz dann mit anderen Sequenzen zusammen und fügen Sie schließlich alles zu einem vollständig sortierten Array zusammen.

Programmimplementierung:

Anhand der obigen Beschreibung sollten Sie denken, dass Sie rekursive Programme verwenden können, um diese Programmierung zu implementieren:

Um dieses Programm zu implementieren, müssen Sie möglicherweise die folgenden Probleme lösen:

So teilen Sie das Array auf:

Setzen Sie zwei Indikatoren, von denen einer auf den Anfang zeigt das Array Unter der Annahme von $left zeigt man auf das letzte Element des Arrays $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);

Nach dem Login kopieren

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

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

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

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

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

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

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