Explication détaillée du tri par bucket dans la série d'algorithmes de tri PHP

Cet article présente principalement en détail le tri par bucket dans la série d'algorithmes de tri PHP. Il a une certaine valeur de référence. Les amis intéressés peuvent se référer à

Tri par bucket

Le tri par compartiment, ou tri par compartiment, 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 le seau correspondant 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;
}

Ce qui précède est l'intégralité du contenu de cet article, j'espère. cela sera utile à l'étude de chacun. J'espère également que tout le monde soutiendra le site Web php chinois.

Articles qui pourraient vous intéresser :

Explication détaillée du tri par fusion des compétences de l'algorithme de tri PHP series_php

Explication détaillée du tri par sélection directe dans la série d'algorithmes de tri PHP

Explication détaillée du tri par insertion dans la série d'algorithmes de tri 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!