Clasificación de montón: usando montones de raíz grandes
Todas las matrices se ingresan en el montón, luego el montón se libera del montón y se inserta nuevamente en la matriz de atrás hacia adelante, y la matriz se ordena de pequeña a grande.
clase pública maxheap <t se extiende comparable <? Super t >> {private t [] datos; tamaño privado int; Capacidad privada int; public maxheap (int capacidad) {this.data = (t []) nuevo comparable [capacidad + 1]; tamaño = 0; this.capacity = capacidad; } public int size () {return this.size; } public boolean isEtimty () {return size == 0; } public int getCapacity () {return this.capacity; } / ** * @return ver la raíz máxima (solo verlo sin eliminación, en comparación con popmax) * / public t Seekmax () {Data de retorno [1]; } public void swap (int i, int j) {if (i! = j) {t temp = data [i]; datos [i] = data [j]; datos [j] = temp; }} public void Insert (t item) {size ++; datos [tamaño] = elemento; ShiftUp (tamaño); } / ** * @return Pop la raíz máxima (emergente significa deleción, en comparación con Seekmax) * / public t popMax () {swap (1, tamaño--); Shiftdown (1); Datos de devolución [tamaño + 1]; } / ** * @param Child La marca de esquina inferior del nodo infantil es el niño, y la tabla de esquina inferior del nodo principal es el niño / 2 * / public void shiftUp (int child) {while (child> 1 && data [child] .compareto (datos [niño / 2])> 0) {swap (niño, niño / 2); niño = niño / 2; }}/*** @param Una marca de esquina inferior de un elemento en la matriz de datos* @param b La marca de esquina inferior de un elemento en la matriz de datos* @return la marca de esquina inferior de la que es grande es grande*/private int max (int a, int b) {if (data [a] .compareto (datos [b]) <0) {/ if data [b] gran retorno B; // return a; // return a}}/*** @param Una marca de esquina inferior de un elemento en la matriz de datos* @param B Marca de esquina inferior de un elemento en la matriz de datos* @param C Marca de esquina inferior de un elemento en la matriz de datos* @return la marca de esquina inferior de un elemento en la matriz de datos*/private int max (int a, int b, int c) {int más grande = max (a, b, b); más grande = max (más grande, c); regresar más grande; }/** * @param Padre La marca de la esquina inferior del nodo principal es el padre, y las tablas de la esquina inferior de la izquierda y la derecha dos nodos infantiles son: padre * 2 y padre * 2 + 1 */public void shiftdown (int padre) {while (true) {int lChild = padre * 2; // hijo int rchild = 2 + 1; // Child int Newfather = Padre; // NEWFATHTER ALTADO. ¿Quién es la marca de la esquina inferior de los nodos de los padres, izquierda y derecha? If (lChild> size) {// Si el nodo padre no tiene regreso infantil ni de niño derecho; } else if (rchild> size) {// Si el nodo padre solo ha dejado el hijo, no hay niño right neoNfather = max (padre, lChild); } else {// si el nodo padre tiene un niño y niño derecho de izquierda neofather = max (padre, lchild, rchild); } if (novato == padre) {// Significa que el padre es más grande que ambos nodos infantiles, y el nombre de la tabla ya es un gran montón de raíz, por lo que no es necesario continuar ajustando el retorno; } else {// de lo contrario, debe continuar ajustando el montón hasta que la condición de montón de raíz grande se cumpla (padre, novato); // value intercambio padre = newfather; // Actualizar el valor del padre, que es equivalente a continuar ajustando el desplazamiento (novato)}}} público estático <t extiende comparable <? Super t >> void sort (t [] arr) {int len = arr.length; // In-Heap maxheap <t> maxheap = new MaxHeap <T> (len); para (int i = 0; i <len; i ++) {maxheap.insert (arr [i]); } // Out-Heap para (int i = len-1; i> = 0; i--) {arr [i] = maxheap.popmax (); }} public static void printarr (objeto [] arr) {for (object o: arr) {system.out.print (o); System.out.print ("/t"); } System.out.println (); } public static void main (string args []) {integer [] 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}}Clasificación de montón: construya el montón en la matriz (montón máximo)
clase pública maxheap <t se extiende comparable <? Super t >> {private t [] datos; tamaño privado int; Capacidad privada int; public maxheap (int capacidad) {this.capacity = capacidad; this.size = 0; this.data = (t []) nuevo comparable [capacidad + 1]; } public maxHeap (t [] arr) {// Heapify, array Heap Capacidad = arr.length; data = (t []) nuevo comparable [Capacidad + 1]; System.ArrayCopy (arr, 0, datos, 1, arr.length); tamaño = 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 isEtimty () {return size == 0; } public t Seekmax () {Data de retorno [1]; } public void swap (int i, int j) {if (i! = j) {t temp = data [i]; datos [i] = data [j]; datos [j] = temp; }} public void Insert (t item) {size ++; datos [tamaño] = elemento; ShiftUp (tamaño); } public t popmax () {swap (1, tamaño--); Shiftdown (1); Datos de devolución [tamaño + 1]; } public void shiftUp (int child) {while (child> 1 && data [child] .compareto (data [child / 2])> 0) {swap (niño, niño / 2); niño /= 2; }}/*** @param una marca de esquina inferior de un elemento en la matriz de datos* @param B Marca de esquina inferior de un elemento en la matriz de datos* @return return ¿Qué elemento es más grande, la marca de esquina inferior de la que es más grande*/private int max (int a, int b) {if (data [a] .compareto (datos [b]) <0) {// if datos [b] big retorno b; datos [a] Big return a; // return a}}/*** @param Una marca de esquina inferior de un elemento en la matriz de datos* @param B Marca de esquina inferior de un elemento en la matriz de datos* @param c La marca de esquina inferior de un elemento en la matriz de datos* @return la marca de la esquina inferior de qué elemento es más grande*/privado int max (int a, int b, int c) {int más grande = max (a, b, b, b, b, b, b); más grande = max (más grande, c); regresar más grande; } public void shiftdown (int padre) {while (true) {int lchild = padre * 2; int rchild = padre * 2 + 1; int Newfather = Padre; // No importa si la tarea se asigna aquí. Si se cambia el siguiente regreso para romper, se debe asignar si (lChild> size) {// si no hay regreso a los niños a la izquierda y a la derecha; } else if (rchild> size) {// Si no hay un niño correcto neofather = max (padre, lChild); } else {// Si hay un niño de izquierda y derecho novato = max (padre, lchild, rchild); } if (novato == padre) {// Si el nodo principal original es el más grande de tres, no necesita continuar ordenando el retorno de la pila; } else {// El nodo principal no es el más grande, intercambia a los niños mayores y continúa ajustando la baja hasta que el montón de raíz grande esté satisfecho (novato, padre); Padre = novato; // equivalente a Shiftdown (novato). Si el novato resulta ser el hijo izquierdo del padre, es equivalente a Shiftdown (2*padre)}}} Public Static <t se extiende comparable <? Super t >> void sort (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 (objeto [] arr) {for (object o: arr) {system.out.print (o); System.out.print ("/t"); } System.out.println (); } public static void main (string args []) {integer [] 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}}El ejemplo de clasificación de montón anterior (implementación de la matriz Java) es todo el contenido que comparto con usted. Espero que pueda darle una referencia y espero que pueda apoyar más a Wulin.com.