Série d'algorithmes de tri PHP tri par seau explication détaillée_compétences php

Cet article présente principalement à tout le monde le tri par buckets de la série d'algorithmes de tri. Il a une certaine valeur de référence. Les amis intéressés peuvent s'y référer.

Tri par compartiment

Le tri par compartiment, ou ce qu'on appelle le tri par boîte, est un algorithme de tri qui fonctionne en divisant les tableaux en un nombre limité de compartiments. Chaque bucket est trié individuellement (il peut être possible d'utiliser un autre algorithme de tri ou de continuer à utiliser le tri par bucket de manière récursive). Le tri par seau est un résultat inductif du tri par compartiments. Le tri par compartiment utilise le temps linéaire (Θ(n)) lorsque les valeurs du tableau à trier sont uniformément réparties. Mais le tri par compartiment n’est pas un tri par comparaison et il n’est pas affecté par la limite inférieure de O(n log n).

Principe

Définissez un tableau quantitatif comme un seau vide.
Recherchez la séquence et placez les éléments dans les seaux correspondants un par un.
Triez chaque seau qui n'est pas vide.
Remettez les éléments du seau qui n'est pas vide dans la séquence d'origine.

Exemple

Supposons les numéros à trier [6 2 4 1 5 9]

Préparez 10 seaux vides, maximum Plusieurs seaux vides
[0 0 0 0 0 0 0 0 0 0] Seaux vides
[0 1 2 3 4 5 6 7 8 9] Numéro du seau (n'existe en fait pas)

1. Retirez les nombres du tableau à trier séquentiellement. Tout d'abord, 6 est retiré, puis 6 est placé dans le seau n° 6. Le processus est similaire à celui-ci : seau vide [tableau à trier [ 0". ] ] = tableau à trier [ 0 ]

[6 2 4 1 5 9] Tableau à trier
[0 0 0 0 0 0 6 0 0 0] Seau vide
[0 1 2 3 4 5 6 7 8 9] Numéro de bucket (n'existe en fait pas)

2 Retirez séquentiellement le numéro suivant du tableau à trier à ce moment-là. est sorti et mis dans le seau n°2, quel que soit son numéro

[6 2 4 1 5 9] Tableau à trier
[0 0 2 0 0 0 6 0. 0 0] Seau vide
[0 1 2 3 4 5 6 7 8 9] Numéro de seau (n'existe en fait pas)

3, 4, 5, 6 sont omis, le processus est pareil, une fois que tout sera mis dans le seau, cela deviendra comme ceci :

[6 2 4 1 5 9] Tableau à trier
[0 1 2 0 4 5 6 0 0 9] Seau vide
[0 1 2 3 4 5 6 7 8 9] Numéro du seau (n'existe pas en fait)
0 signifie seau vide, sautez-le, sortez-le simplement dans l'ordre : 1 2 4 5 6 9

Implémentation du code PHP

<?php
function bucket_sort($arr){
 $result=[];
 $length=count($arr);
 //入桶
 for($i=0,$max=$arr[$i];$i<$length;$i++){
  if ($max<$arr[$i]) {
   $max=$arr[$i];
  }
  $bucket[$arr[$i]]=[];
  array_push($bucket[$arr[$i]],$arr[$i]);
 }
 //出桶
 for($i=0;$i<=$max;$i++){
  if(!empty($bucket[$i])){
   $l=count($bucket[$i]);
   for ($j=0; $j <$l ; $j++) {
    $result[]=$bucket[$i][$j];
   }
  }
 }
 return $result;
}

Recommandations associées :

Calcul de la période d'ovulation méthode Révision et résumé de l'algorithme de tri PHP

Révision et résumé de l'algorithme de tri PHP_Tutoriel PHP

algorithme de tri php ?algorithme de tri php classique_Tutoriel PHP

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!