Préface: le sujet des structures de données Java et des algorithmes sera mis à jour de temps à autre. Les lecteurs sont les bienvenus pour le superviser. Cet article commence par l'algorithme de tri le plus simple - le tri du seau et analyse les idées d'implémentation, la mise en œuvre du code, les caractéristiques de performance et les scénarios applicables de tri du seau.
0. Autres index algorithmes de tri
//www.vevb.com/article/120879.htm
1. Idée de tri du seau
Un exemple simple:
Tri des résultats des tests en anglais de 6 personnes (1 ~ 10 points). Si le score est [6, 5, 8, 8, 10, 9], l'idée du tri avec des seaux est de préparer 10 seaux, les nombres sont de 1 ~ 10 dans une séquence, et les scores sont placés dans les seaux correspondants, tels que 6 points dans le seau n ° 6, et deux points de 8 points dans le n ° 8 ... et ensuite les produire un par un seul nombre de nombres (s'il y a, s'il y a, s'il n'y a pas, il n'y a pas. C'est l'idée de base du tri du seau.
En fait, ce n'est qu'une version simple. Imaginez-vous, si la gamme d'éléments à tri est relativement grande, comme 1 ~ 10 000, avez-vous besoin de 10 000 seaux? En fait, dans ce cas, un élément n'est pas toujours placé dans un seau, mais plusieurs fois plusieurs éléments sont placés dans un seau. En fait, le véritable tri et la liste de hachage du seau ont le même principe.
Dans le tri réel, les éléments de chaque seau sont généralement triés à l'aide d'autres algorithmes de tri, donc plus souvent, le tri du seau est utilisé en combinaison avec d'autres algorithmes de tri.
2. Code de tri du seau
Après avoir analysé l'idée du tri du seau, vous devez d'abord connaître la gamme d'éléments à tri. Prenant ce qui précède comme exemple, déclarez un tableau de longueur 10 comme 10 seaux, puis mettez les résultats un par un dans le godet, la valeur du seau est +1, et enfin la sortie de l'indice du tableau dans l'ordre inverse. La valeur de chaque position du tableau est sortie plusieurs fois, de sorte que le tri de base de base peut être obtenu.
classe publique Backetort {Bucket int [] privé; Array int [] privé; public backetort (int gage, int [] array) {this.buckets = new int [range]; this.array = array; } / * Tri * / public void tri () {if (array! = Null && array.length> 1) {for (int i = 0; i <array.length; i ++) {bucket [array [i]] ++; }}} / * Tri de sortie * / public void sortout () {// Données de sortie inverse pour (int i = bucket.length-1; i> = 0; i -) {for (int j = 0; j <bucket [i]; j ++) {System.out.print (i + "/ t"); }}}}Code de test:
classe publique SortTest {public static void main (String [] args) {TestBuckeTsSort (); } private static void testBucketsSort () {int [] array = {5,7,3,5,4,8,6,4,1,2}; Backetort BS = new Backetort (10, tableau); bs.sort (); bs.sortout (); // Sortie d'impression de sortie}}3. Caractéristiques de performance de tri du seau
Le tri du seau ne nécessite en fait que l'itération à travers tous les éléments pour être triés, puis les mettre en position spécifiée en séquence. Si le temps de tri de sortie est ajouté, tous les seaux doivent être traversés. Par conséquent, la complexité temporelle du tri du seau est O (n + m), n est le nombre d'éléments à tri, et m est le nombre de seaux, c'est-à-dire la plage d'éléments à tri. Cet algorithme est un algorithme de tri très rapide, mais la complexité spatiale est relativement grande.
Lorsque la plage de taille des éléments à disposer est relativement grande, mais le nombre d'éléments à disposer est relativement faible, les déchets d'espace sont plus graves. La distribution des éléments à organiser est uniforme chaque mois, et plus le taux d'utilisation de l'espace est élevé, cela est en fait rare.
Grâce à l'analyse des performances ci-dessus, nous pouvons obtenir les caractéristiques du tri du seau: rapide et simple, mais en même temps, l'utilisation de l'espace est faible. Lorsque les données à tri est grande, le taux d'utilisation de l'espace est insupportable.
4. Tri de seau Scénarios applicables
Selon les caractéristiques du tri du seau, le tri du seau est généralement applicable à certains environnements spécifiques, tels que la plage de données est relativement limité ou il existe des exigences spécifiques, telles que la nécessité d'obtenir rapidement certaines valeurs par le mappage de hachage, et le nombre de chaque nombre doit être compté. Mais tout cela est basé sur la confirmation de la portée des données. Si la portée de la portée est trop grande, envisagez d'utiliser d'autres algorithmes.