Tri de tas: en utilisant de grands tas de racines
Tous les tableaux sont entrés dans le tas, puis le tas est libéré du tas et inséré dans le tableau de l'arrière à l'avant, et le tableau est commandé de petit à grand.
La classe publique Maxheap <t s'étend comparable <? Super T >> {Données privées T []; Taille INT privée; capacité int privée; public maxheap (int la capacité) {this.data = (t []) new comparable [capacité + 1]; taille = 0; this.capacity = capacité; } public int size () {return this.size; } public boolean isEmpty () {return size == 0; } public int getCapacity () {return this.capacity; } / ** * @return Voir la racine maximale (ne le voir que sans suppression, par rapport à popmax) * / public t SeekMax () {return data [1]; } public void swap (int i, int j) {if (i! = j) {t temp = data [i]; data [i] = data [j]; data [j] = temp; }} public void insert (t item) {size ++; data [size] = item; ShifUp (taille); } / ** * @return pop la racine maximale (la popup signifie la suppression, par rapport à SeekMax) * / public t popmax () {swap (1, size--); décalage (1); Retour des données [taille + 1]; } / ** * @param enfant La marque d'angle inférieure du nœud enfant est l'enfant, et le tableau d'angle inférieur du nœud parent est l'enfant / 2 * / public void shipUp (int enfant) {while (enfant> 1 && data [enfant] .compareto (data [enfant / 2])> 0) {swap (enfant, enfant / 2); enfant = enfant / 2; }} / ** * @param Une marque d'angle inférieure d'un élément dans le tableau de données * @param b la marque d'angle inférieure d'un élément dans le tableau de données * @return la marque d'angle inférieure dont l'élément est grand * / privé int max (int a, int b) {if (data [a] .compareto (data [b]) <0) {// if data [b] Big return b; / return b} retourner a; // return a}} / ** * @param Une marque de coin inférieure d'un élément dans le tableau de données * @param b marque de coin inférieur d'un élément dans le tableau de données * @param c marc de coin inférieur d'un élément dans le tableau de données * @return la marque de coin inférieure d'un élément dans le tableau de données * / private int max (int, int b, int c) {int biggel = max (a, b); plus grand = max (plus grand, c); retourner plus grand; } / ** * @param père La marque de coin inférieure du nœud parent est le père, et les tables d'angle inférieur des deux nœuds de gauche et de droite sont: père * 2 et père * 2 + 1 * / public void shiftdown (int père) {while (true) {int lChild = père * 2; // Left Child int rChild = père * 2 + 1; // rectère intra newfather = père; // newfather est à propos de la mise à jour. Qui est la marque d'angle inférieure du parent, les nœuds gauche et droit? If (lChild> size) {// Si le nœud père n'a ni enfant de gauche ni enfant droit; } else if (rChild> size) {// Si le nœud père n'a que l'enfant gauche, pas d'enfant droit newfather = max (père, lchild); } else {// Si le nœud père a à la fois un enfant gauche et un enfant droit newfather = max (père, lchild, rchild); } if (newfather == père) {// Cela signifie que le père est plus grand que les deux nœuds enfants, et le nom du tableau est déjà un grand tas de racine, il n'est donc pas nécessaire de continuer à ajuster le retour; } else {// Sinon, vous devez continuer à ajuster le tas jusqu'à ce que la condition du tas de racine soit satisfait Swap (père, newfather); // Value Exchange père = newfather; // Mettez à jour la valeur du père, ce qui équivaut à continuer à ajuster ShiftDown (newfather)}}} public static <t s'étend comparable <?? super t >> void tri (t [] arr) {int len = arr.length; // in-heap maxheap <T> maxHeap = new maxHeap <T> (len); pour (int i = 0; i <len; i ++) {maxHeap.insert (arr [i]); } // out-heap pour (int i = len - 1; i> = 0; i--) {arr [i] = maxheap.popMax (); }} public static void printarr (objet [] arr) {for (objet o: arr) {System.out.print (o); System.out.print ("/ t"); } System.out.println (); } public static void main (String args []) {entier [] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6}; printarr (arr); // 3 5 1 7 2 9 8 0 4 6 Sort (arr); printarr (arr); // 0 1 2 3 4 5 6 7 8 9}}Tri du tas: construire le tas sur le tableau (tas maximum)
La classe publique Maxheap <t s'étend comparable <? Super T >> {Données privées T []; Taille INT privée; capacité int privée; public maxheap (int la capacité) {this.capacity = capacité; this.size = 0; this.data = (t []) nouveau comparable [capacité + 1]; } public maxHeap (t [] arr) {// taspify, array tas capacity = arr.length; data = (t []) Nouveau comparable [capacité + 1]; System.ArrayCopy (Arr, 0, Data, 1, Arr.Length); size = arr.length; for (int i = size / 2; i> = 1; i--) {shiftDown (i); }} public int size () {return this.size; } public int getCapacity () {return this.capacity; } public boolean isEmpty () {return size == 0; } public t SeekMax () {return data [1]; } public void swap (int i, int j) {if (i! = j) {t temp = data [i]; data [i] = data [j]; data [j] = temp; }} public void insert (t item) {size ++; data [size] = item; ShifUp (taille); } public t popmax () {swap (1, size--); décalage (1); Retour des données [taille + 1]; } public void shipUp (int child) {while (enfant> 1 && data [enfant] .compareto (data [enfant / 2])> 0) {swap (enfant, enfant / 2); enfant / = 2; }} / ** * @param Une marque d'angle inférieure d'un élément dans le tableau de données * @param b marque de coin inférieur d'un élément dans le tableau de données * @return return quel élément est plus grand, la marque de coin inférieure dont l'élément est plus grand * / privé int max (int a, int b) {if (data [a] .compareto (data [b]) <0) {// si les données [b] big b; Données [A] Big Return A; // Renvoie A}} / ** * @param Une marque de coin inférieure d'un élément dans le tableau de données * @param B Bas Corner Mark d'un élément dans le tableau de données * @param C la marque d'angle inférieure d'un élément dans le tableau de données * @return la marque de coin inférieure dont l'élément est plus grand * / privé int Max (int a, int b, int c) {int bancal = max (a, b); plus grand = max (plus grand, c); retour plus grand; } public void shipdown (int père) {while (true) {int lChild = père * 2; int rchild = père * 2 + 1; int newfather = père; // peu importe si la mission est attribuée ici. Si le rendement suivant est modifié en cassant, il doit être attribué si (lChild> taille) {// s'il n'y a pas d'enfants à gauche et à droite renvoient; } else if (rchild> size) {// s'il n'y a pas de bon enfant newfather = max (père, lChild); } else {// s'il y a un enfant gauche et droit newfather = max (père, lchild, rchild); } if (newfather == père) {// Si le nœud parent d'origine est le plus grand des trois, vous n'avez pas besoin de continuer à régler le retour du pile; } else {// Le nœud parent n'est pas le plus grand, échangez les enfants plus âgés et continuez à ajuster la baisse jusqu'à ce que le grand tas de racine soit satisfait d'échange (nouveau, père); père = nouveau-père; // équivalent à Switchdown (nouveau). Si le nouveau se révèle être l'enfant gauche du père, il est équivalent à Shiftdown (2 * père)}}} public statique <t s'étend comparable <? super t >> void tri (t [] arr) {int len = arr.length; MaxHeap <T> maxHeap = new maxHeap <> (arr); for (int i = len - 1; i> = 0; i--) {arr [i] = maxHeap.popMax (); }} public static void printarr (objet [] arr) {for (objet o: arr) {System.out.print (o); System.out.print ("/ t"); } System.out.println (); } public static void main (String args []) {entier [] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6}; printarr (arr); // 3 5 1 7 2 9 8 0 4 6 Sort (arr); printarr (arr); // 0 1 2 3 4 5 6 7 8 9}}L'exemple de tri de tas ci-dessus (implémentation Java Array) est tout le contenu que je partage avec vous. J'espère que vous pourrez vous faire référence et j'espère que vous pourrez soutenir Wulin.com plus.