Qu'est-ce que le tri par compartiment

Le tri par compartiments est un algorithme de tri. Le principe de fonctionnement est de diviser le tableau en un nombre limité de compartiments. Le tri par compartiments est également un résultat inductif du tri par compartiments. are Lorsqu'il est distribué uniformément, le tri par compartiment utilise un temps linéaire, mais le tri par compartiment n'est pas un tri par comparaison et il n'est pas affecté par la limite inférieure « O(n log n) ».

Tri par bucket

Si l'on sait que la plage de valeurs de N mots-clés est de 0 à entre M-1 et M est beaucoup plus petit que N, l'algorithme de tri par bucket crée un « bucket » pour chaque valeur du mot-clé, c'est-à-dire que M buckets sont créés lors de l'analyse de N mots-clés, chaque clé met les mots dans le correspondant. seaux, puis les collecter dans l'ordre des seaux à ordonner naturellement

Introduction :

Le tri par seau, ou ce qu'on appelle le tri par boîte, est un algorithme de tri, le principe de fonctionnement est de divisez le tableau en un nombre limité de compartiments. Chaque bucket est trié individuellement (il est possible d'utiliser d'autres algorithmes de tri ou de continuer à utiliser le tri par buckets 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 O(n log n).

Définition

Hypothèse : L'entrée est un nombre réel uniformément distribué dans l'intervalle [0, 1) généré par un processus aléatoire. Divisez l'intervalle [0, 1) en n sous-intervalles (seaux) de taille égale, chaque taille de seau est 1/n : [0, 1/n), [1/n, 2/n), [2/n , 3/n),…,[k/n, (k+1)/n),…distribuer n éléments d'entrée à ces compartiments, trier les éléments dans les compartiments, puis connecter les compartiments en séquence pour entrer 0 ≤A [1 ..n] <1 Le tableau auxiliaire B[0..n-1] est un tableau de pointeurs pointant vers le compartiment (liste chaînée).

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!