Comment implémenter le tri par fusion en PHP

Cet article présente principalement l'algorithme d'implémentation du tri par fusion PHP, c'est-à-dire diviser la séquence à trier en plusieurs sous-séquences ordonnées, puis fusionner les sous-séquences ordonnées en une séquence ordonnée globale. Les amis intéressés peuvent venir le découvrir.

La méthode de tri par fusion consiste à fusionner deux (ou plus) listes ordonnées en une nouvelle liste ordonnée. Un inconvénient du tri par fusion est qu'il nécessite de la mémoire pour un autre tableau de taille égale au nombre d'éléments de données. Si le tableau initial occupe presque toute la mémoire, le tri par fusion ne fonctionnera pas, mais s'il y a suffisamment d'espace, le tri par fusion peut être un bon choix.

Supposons que la séquence soit triée :

4 3 7 9 2 8 6

Laissez-moi d'abord parler de l'idée. L'idée centrale du tri par fusion est de fusionner deux séquences triées en une seule séquence triée.

La séquence ci-dessus peut être divisée en :

4 3 7 9
et
2 8 6

ces deux séquences, puis trier les deux séquences séparément : le résultat est :

est défini sur la séquence A, et la séquence B,

3 4 7 9
2 6 8

Fusionner les deux séquences ci-dessus en une seule séquence triée :

L'idée spécifique de​​fusionner est :

Définissez deux indicateurs de position, pointant respectivement vers les positions de départ de la séquence A et de la séquence B : le rouge est la position où pointe l'indicateur :

3 4 7 9
2 6 8

Comparez les valeurs des éléments pointés par les deux indicateurs, insérez le plus petit dans un nouveau tableau, tel que la séquence C, et déplacez le indicateur correspondant en arrière en même temps Un bit :
Le résultat est :

3 4 7 9
2 6 8

Séquence C formée : Un élément a été inséré. Le plus petit élément 2.
2

est ensuite comparé à nouveau avec l'élément pointé par l'indicateur dans la séquence A. et séquence B : le petit Mettez-le dans la séquence C et déplacez le pointeur correspondant Le résultat est :

3 4 7 9
2 6 82 3

Et ainsi de suite, exécutez de manière itérative jusqu'à ce qu'un indicateur de la séquence A ou de la séquence B se soit déplacé vers la fin du tableau. Par exemple :

Après plusieurs comparaisons, la séquence B a déplacé l'indicateur à la fin de la séquence (après le dernier élément).
3 4 7
9
2 6 82 3 4 6 7 8

Ensuite, il y aura des séquences inutilisées, qui sont le reste de la séquence A Tous les des éléments peuvent être insérés après la séquence C. Il n'en reste qu'un 9. Insérez-le après la séquence C :

Résultat de la séquence C :

2 3 4 5 6. 7 8 9

De cette façon, l'opération de fusion de deux séquences ordonnées en une seule séquence ordonnée est réalisée

Regardons d'abord cette fusion du code 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;
}

Après l'analyse ci-dessus et la mise en œuvre du programme, il n'est pas difficile de constater que le temps de fusion des séquences triées doit être linéaire, c'est-à-dire qu'au plus N-1 comparaisons auront lieu, où N est la somme de tous les éléments.

Grâce à la description ci-dessus, nous avons implémenté le processus de sommation de deux tableaux triés.

À ce stade, vous vous posez peut-être des questions : qu'est-ce que cela a à voir avec toute la séquence de tri par fusion ? Ou comment avez-vous obtenu les deux premières sous-séquences triées ?

Ensuite, nous décrirons ce qu'est le tri par fusion, puis examinerons la relation entre la fusion et le tri par fusion ci-dessus :

Autant y penser, lorsque nous devons trier le tableau suivant, pouvons-nous d'abord fusionner et trier la première moitié du tableau et la seconde moitié du tableau, puis fusionner les résultats triés ?

Par exemple : Tableau à trier :

4 3 7 9 2 8 6

Divisez d'abord en 2 parties :

4 3 7 9

2 8 6

Considérez la première moitié et la seconde moitié comme une séquence et effectuez à nouveau l'opération de fusion (c'est-à-dire diviser, trier, fusionner)

deviendra En :

Devant :

4 3
7 9

Dos :

2 8
6

De même, fusionnez et triez à nouveau chaque auto-séquence (diviser, trier, fusionner).

Lorsqu'il n'y a qu'un seul élément (longueur 1) dans la sous-séquence divisée, alors la séquence n'a plus besoin d'être divisée et devient un tableau trié. Fusionnez ensuite cette séquence avec d'autres séquences, et enfin fusionnez le tout dans un tableau trié complet.

Mise en œuvre du programme :

À travers la description ci-dessus, vous devriez penser que vous pouvez utiliser des programmes récursifs pour mettre en œuvre cette programmation :

Pour mettre en œuvre ce programme, vous devrez peut-être résoudre les problèmes suivants :

Comment diviser le tableau :

Définissez deux indicateurs, l'un pointant vers le début de le tableau En supposant $left, on pointe vers le dernier élément du tableau $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，因此会浪费一些资源。因此在实际的排序中还是 相对的较少使用。

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

相关推荐：

PHP使用curl_multi实现并发请求的方法示例

PHP性能测试工具xhprof安装与使用方法详解

PHP实现通过strace定位故障原因的方法

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!