Maison >développement back-end >tutoriel php >Comment implémenter le tri par tableau en PHP : tri rapide, tri par insertion, algorithme de tri par fusion

Comment implémenter le tri par tableau en PHP : tri rapide, tri par insertion, algorithme de tri par fusion

不言
不言original
2018-07-19 14:20:421648parcourir

Il existe de nombreuses façons de trier des tableaux en PHP, et chaque tri de tableau a ses propres principes différents. Examinons de plus près les exemples d'algorithme de tri rapide, d'algorithme de tri par fusion et d'algorithme de tri par insertion.

Parcours de tableaux de formes spéciales

Trouver la moyenne des nombres dans le tableau suivant :

$arr1 = array(
1, 2, array(31, 32, 33), 4,
array(51, 52, 53, array(541, 542, 543, 544) ),
6, array(71, 72, 73),
);
$count = 0; //计数
$sum = GetArraySum($arr1);
echo “\

Algorithme de tri rapide

Description du principe :

Pour un tel tableau : [5, 1,2, 6,7];

Sortez le premier élément ( et utilisez-le comme tableau intermédiaire), et après avoir comparé les éléments restants avec lui, divisez-le en deux tableaux :

L'élément de tableau de gauche est plus petit que l'élément du milieu et l'élément de tableau de droite n'est pas plus petit que l'élément du milieu.

Si le tableau de gauche et le tableau de droite sont déjà des tableaux triés, fusionnez ces trois pour obtenir le résultat final.

Si le tableau de gauche et le tableau de droite ne sont pas encore des tableaux triés, continuez à utiliser cette fonction de manière récursive pour obtenir les tableaux ordonnés.

Schéma schématique :

Comment implémenter le tri par tableau en PHP : tri rapide, tri par insertion, algorithme de tri par fusion

Données principales :

$arr1 = [5, 2, 1, 6,7] ; Données qui illustrent fortement le principe 1

Petit : [2, 1], grand : [6, 7], milieu : [5]

Combiner les trois : [1, 2, 5 , 6, 7];

$arr1 = [2, 1]; //Données qui illustrent fortement le principe 2

Milieu : [2], gauche : [1] , []

Cas spécifique :

$arr1 = [5, 2, 4, 6, 1, 3];
$arr1 = [5, 2, 4, 6, 1, 3];
//$arr1 = [5, 3, 2, 8, 7];
echo “\

Algorithme de tri par insertion

Description du principe :

Pour un tel tableau : [2, 3, 4, 1];

Pour insérer un certain nombre n dans un tableau trié,

il suffit d'ajouter n suivi des éléments du tableau de l'arrière vers l'avant Comparez les précédents un par un. Tant qu'un élément s'avère plus grand que n,

reculera l'élément d'une place, puis continuera à le retirer et à le comparer. S'il est plus grand que n, le reculera d'une place. lieu, et ainsi de suite.

Lorsqu'il n'y a pas de valeur supérieure à n à la fin, mettez n dans la position qui a été libérée lorsque vous êtes revenu tout à l'heure.

Pour un tableau, le premier élément peut être considéré comme un tableau "trié",

Ensuite, le deuxième élément peut être "inséré trié" selon le principe ci-dessus, donc les deux précédents peuvent être trié,

et devenir un "tableau trié" avec deux éléments. Vient ensuite l’analogie.

Diagramme schématique :

Comment implémenter le tri par tableau en PHP : tri rapide, tri par insertion, algorithme de tri par fusion

Données principales :

$arr1 = [2, 3, 4, 1] //Explication forte ; Données principales 1

$arr1 = [2, 3, 1]; // Données qui illustrent efficacement le principe 2

$arr1 = [2, 1]; Données 3

$arr1 = [1, 2]; //Données 3 qui illustrent efficacement le principe

Cas particulier :

$arr1 = [5, 2, 4, 6, 1, 3];
$arr1 = [2, 3, 4, 1];
$arr1 = [2, 4, 5, 6, 1, 3];
echo “\

Algorithme de tri par fusion

Description du principe :

Pour un tel tableau : $arr1 = [1, 3, 5, 2, 4, 6] ; divisez-le en deux : $a = [1 , 3, 5],
$b = [2, 4, 6];

S'il y a deux tableaux qui ont été triés, effectuez les opérations suivantes sur les deux tableaux, vous pouvez obtenir un tri "tableau de fusion" des deux tableaux :

Retirez le premier élément a1 du tableau a, puis retirez le premier élément b1 du tableau b, et comparez les tailles a1 et b1,

et placez le petit (supposé être a1) dans un nouveau tableau, et supprimez le premier élément du tableau correspondant a,

puis retirez le premier élément du tableau correspondant (pas les données pour l'instant) , puis continuez à comparer la taille des deux

à chaque fois dans un nouveau tableau, et continuez le prochain "supprimer, récupérer, comparer". . . .

Le résultat final est que vous pouvez obtenir un nouveau tableau trié dans le nouveau tableau.

Pour un tableau qui n'a pas encore été trié, tant qu'il est divisé récursivement en deux, vous obtiendrez finalement le tableau le plus court - une seule ou 0 cellule. Ce type de tableau est naturellement trié. commande.

Diagramme schématique :

Comment implémenter le tri par tableau en PHP : tri rapide, tri par insertion, algorithme de tri par fusion

Données principales :

$arr1 = [1, 3, 5, 4, 6, 7, 8 ]; //La donnée 1 qui illustre effectivement le principe

est divisée en 2 à partir du milieu : [ ]; , ]

$arr1 = [1, 3, 2, 4]; //Donnée 2 qui illustre efficacement le principe

Cas démo :


Recommandations associées :
$arr1 = [5, 2, 4, 6, 1, 3];
echo “\


tri rapide par bulles php, tri par bulles php

partage de la méthode de tri des tableaux php (bulle trier, trier par sélection)

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!

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn