Explication détaillée de la méthode de tri par compartiment de l'algorithme de complétion des nombres Java

Cet article présente principalement la structure de données Java et la méthode de mise en œuvre du tri par compartiments.Il analyse en détail le concept, le principe, la méthode de mise en œuvre et les compétences opérationnelles associées du tri par compartiments avec des exemples spécifiques.Les amis dans le besoin peuvent s'y référer

.

L'exemple de cet article décrit la méthode d'implémentation du tri par compartiment de la structure de données et de l'algorithme Java. Partagez-le avec tout le monde pour votre référence, comme suit :

Idée de base :

Supposons que l'entrée soit générée par un processus aléatoire [0 , M ) nombres réels uniformément répartis sur l'intervalle. Divisez l'intervalle [0, M) en n sous-intervalles (buckets) de taille égale, allouez n éléments d'entrée à ces buckets, triez les éléments dans les buckets, puis connectez les entrées du bucket 0 ≤ A[1.. n] ArrayB[0..n-1] est un tableau de pointeurs pointant vers le bucket (liste chaînée). Distribuez n enregistrements dans chaque compartiment. Si plusieurs enregistrements sont affectés au même compartiment, un tri au sein du compartiment est requis. Enfin, répertoriez les enregistrements de chaque compartiment dans l'ordre et mémorisez-les dans un ordre ordonné.

[Bucket - Keyword] MappingFonction

bindex=f(key) Où, bindex est le bucket Le indice du tableau B (c'est-à-dire le bucket bindex), k est la clé de la colonne à trier. La clé de l'efficacité du tri par bucket réside dans cette fonction de cartographie, qui doit faire : Si le mot-clé k1Évidemment, La détermination de la fonction de mappage a une grande relation avec les caractéristiques des données elles-mêmesDonnons un exemple ci-dessous :

Si la colonne à trier K= {. 49, 38, 35, 97, 76, 73, 27, 49}. Ces données sont toutes comprises entre 1 et 100. Par conséquent, nous personnalisons 10 compartiments et déterminons la fonction de mappage f(k)=k/10. Ensuite le premier mot-clé 49 sera positionné dans le 4ème bucket (49/10=4). Empilez tous les mots-clés dans des compartiments tour à tour et effectuez un tri rapide dans chaque compartiment non vide pour obtenir l'image suivante :

Tant que l'ordre de l'image ci-dessus est Sortie les données dans chaque B[i] pour obtenir une séquence ordonnée.

Le code de base de l'algorithme est le suivant :

/// <summary>
/// 桶排序
///
///如果有重复的数字,则需要 List<int>数组,这里举的例子没有重复的数字
/// </summary>
/// <param name="unsorted">待排数组</param>
/// <param name="maxNumber">待排数组中的最大数,如果可以提供的话</param>
/// <returns></returns>
static int[] bucket_sort(int[] unsorted, int maxNumber = 97)
{
 int[] sorted = new int[maxNumber + 1];
 for (int i = 0; i < unsorted.Length; i++)
 {
  sorted[unsorted[i]] = unsorted[i];
 }
 return sorted;
}
static void Main(string[] args)
{
 int[] x = {49、 38 、 35、 97 、 76、 73 、 27、 49 };
 var sorted = bucket_sort(x, 97);
 for (int i = 0; i < sorted.Length; i++)
 {
  if (sorted[i] > 0)
   Console.WriteLine(sorted[i]);
 }
 Console.ReadLine();
}

Analyse des coûts de tri des seaux

Le tri par bucket utilise la relation de mappage des fonctions pour réduire presque tout le travail de comparaison. En fait, le calcul de la valeur f(k) du tri par compartiments équivaut à la division en tri rapide, qui a divisé une grande quantité de données en blocs de données fondamentalement ordonnés (seaux). Ensuite, il vous suffit d'effectuer un tri par comparaison avancé sur une petite quantité de données dans le bucket.

La complexité temporelle du tri des buckets de N mots-clés est divisée en deux parties :

(1) BoucleCalculez le bucket de chaque mot-clé Fonction de cartographie, cette fois la complexité est O(N).
(2) Utilisez l'algorithme de tri par comparaison avancé pour trier toutes les données de chaque compartiment, et sa complexité temporelle est ∑ O(Ni*logNi). Où Ni est le volume de données du i-ième compartiment.

Évidemment, la partie (2) est le facteur déterminant dans la performance du tri par seau. Minimiser le nombre de données dans le compartiment est le seul moyen d'améliorer l'efficacité (car la meilleure complexité temporelle moyenne basée sur le tri par comparaison ne peut atteindre que O(N*logN)). Par conséquent, nous devons faire de notre mieux pour atteindre les deux points suivants :

(1) La fonction de cartographie f(k) peut répartir uniformément N données dans M buckets, de sorte que chaque bucket ait [ N /M] quantité de données.
(2) Augmentez le nombre de seaux autant que possible. Dans le cas extrême, une seule donnée peut être obtenue de chaque compartiment, évitant ainsi complètement l'opération de tri par « comparaison » des données dans le compartiment. Bien sûr, ce n'est pas facile à faire. Lorsque la quantité de données est énorme, la fonction f(k) entraînera un grand nombre d'ensembles de compartiments, ce qui entraînera un grave gaspillage d'espace. Il s’agit d’un compromis entre le coût du temps et le coût de l’espace.

Pour N données à trier et M buckets, la complexité moyenne du temps de tri des buckets de [N/M] données par bucket est :

O (N)+ O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)

Quand N=M, c'est-à-dire dans le cas extrême, il n'y a qu'une seule donnée dans chaque bucket. La meilleure efficacité du tri par seau peut atteindre O(N).

Résumé : La complexité temporelle moyenne du tri des seaux est linéaire O(N+C), où C=N*(logN-logM). Si par rapport au même N, plus le nombre de compartiments M est grand, plus l'efficacité est élevée et la meilleure complexité temporelle atteint O(N). Bien sûr, la complexité spatiale du tri par buckets est O(N+M). Si les données d'entrée sont très volumineuses et que le nombre de buckets est également très grand, le coût de l'espace sera sans aucun doute élevé. De plus, le tri par seau est stable.

C'est-à-dire les trois points suivants :

1. Le tri au seau est stable
2. Le tri au seau est le plus rapide parmi les tris courants, meilleur que le tri rapide. Encore plus rapide... dans la plupart des cas
3. Le tri par buckets est très rapide, mais il consomme également beaucoup d'espace. C'est fondamentalement l'algorithme de tri le plus gourmand en espace

.

Supplément : Dans l'algorithme de recherche, la meilleure complexité temporelle de l'algorithme de recherche basé sur la comparaison est également O(logN). Par exemple, recherche binaire, arbre binaire équilibré, arbre rouge-noir, etc. Cependant, la table Hash a une efficacité de recherche de niveau linéaire O(C) (l'efficacité de recherche atteint O(1) sans conflits). Alors : l'idée de la table de hachage est-elle similaire au tri par buckets ?

En fait, le tri par buckets a des exigences particulières en matière de conditions de données. Si le tableau est grand, des centaines de millions de buckets seront évidemment alloués. impossible. Par conséquent, le tri par compartiment a ses limites et convient aux situations où l'ensemble des valeurs d'éléments n'est pas important.

【Recommandations associées】

1. Recommandation spéciale : Téléchargement de la version V0.1 de "php Programmer Toolbox"

2. Tutoriel vidéo Java gratuit

2 Analyse complète des annotations Java

.

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!