Concepto de algoritmo de clasificación rápida
La clasificación rápida generalmente se basa en la implementación recursiva. La idea es la siguiente:
1. Seleccione un valor apropiado (el valor ideal es el mejor, pero el primer valor en la matriz generalmente se usa en la implementación), que se llama "pivote".
2. Basado en este valor, divida la matriz en dos partes, la parte más pequeña a la izquierda y la parte más grande a la derecha.
3. Es cierto que después de tal ronda, la posición de este pivote debe estar en la posición final.
4. Repita el proceso anterior para las dos subarrías hasta que solo haya un elemento por matriz.
5. La clasificación se completa.
Método de implementación básica:
public static void Quicksort (int [] arr) {Qsort (arr, 0, arr.length-1);} private static void qsort (int [] arr, int low, int high) {if (low <high) {int pivot = partition (arr, bajo, alto); // divide la matriz en dos partes Qsort (arr, baja, pivot-1); // Ordenar la subarray izquierda Qsort (arr, pivot+1, alto); // Ordenar la subarray derecha recursivamente}} private static int particion (int [] arr, int low, int high) {int pivot = arr [low]; // récord de pivote mientras (bajo <high) {while (bajo <high && arr [high]> = pivot) --high; arr [bajo] = arr [alto]; // intercambiar registros más pequeños que el pivote a la izquierda, mientras que (bajo <high && arr [bajo] <= pivot) ++ baja; arr [alto] = arr [bajo]; // Intercambio registros más pequeños que el pivote al extremo derecho} // escanear se completa, y el pivote está en su lugar arr [bajo] = pivot; // devuelve la posición del pivote al retorno bajo;}Use genéricos para implementar un algoritmo de orden rápido
A continuación se muestra una clase QuickSort, que contiene la función de función estática (), que puede clasificar las matrices de cualquier tipo. Si se trata de una matriz de tipos de objetos, el tipo de objeto debe implementar la interfaz comparable para que la función Comparisonto pueda usarse para la comparación.
Se usó el algoritmo de clasificación de fila rápida más básica y no se realizó un procesamiento de optimización.
El código fuente es el siguiente:
import java.util.linkedList; import java.util.list; import java.util.listiterator; import java.util.random; Public Class Quicksort {@SupplesSwarnings ("sin verificar") // Modifique el prototipo de función de fila rápida anterior para que pueda clasificar las matrices de cualquier tipo de objeto. Esta función se usa internamente, y la interfaz de función de clasificación externa es sort (). La función de clasificación requiere que el objeto debe implementar la interfaz comparable, que puede proporcionar detección de tipo de compilación, consulte el siguiente artículo. Private static void Quicksort (objeto [] in, int begin, int end) {if (begin == end || begin == (end-1)) return; Objeto p = en [begin]; int a = begin +1; int b = a; para (; b <end; b ++) {// Esta matriz de tipo de objeto debe implementar la interfaz comparable para que pueda usar la función Compareto para la comparación if (((comparable <pectem>) en [b]). Compareto (p) <0) {if (a == b) {a ++; continuar;} objeto temp = en [a]; en [a] = en [b]; en [b] = temp; a ++; }} en [begin] = en [a-1]; en [A-1] = P; if (a-1> begin) {Quicksort (in, begin, a); } if (end-1> a) {Quicksort (in, a, end); } devolver; } // Use genéricos para ordenar cualquier matriz de objeto, la matriz de tipo de objeto debe implementar la interfaz comparable pública estática <t se extiende comparable <? Super t >> void sort (t [] entrada) {Quicksort (entrada, 0, input.length); } // Agregue la función de la clasificación de los objetos de la lista, consulte la función Sort () de la clase Java.util.Collections en Java Public Static <t se extiende comparable <? Super t >> void sort (list <t> list) {object [] t = list.toarray (); // Convertir la lista en una matriz rápida (t, 0, t.length); // Ordenar la matriz // Después de completar la clasificación de la matriz, vuelva a escribir a la lista listiterator <T> i = list.ListIterator (); for (int j = 0; j <t.length; j ++) {I.Next (); i.set ((t) t [j]); }} // Debido a que los genéricos no se pueden usar en Java, tipos de datos primitivos (int, double, byte, etc.), solo puede usar el mecanismo de sobrecarga de funciones para ordenar estas matrices primitivas (int [], double [], byte [], etc.). Para compartir la misma función de clasificación, el mecanismo de tipo original (autoboxing, unboxing) se usa para encapsularla en el tipo de objeto correspondiente, formar una nueva matriz de objeto, ordenarlo y luego desencapsularlo. La desventaja de esto es que requiere pasos de conversión adicionales y espacio adicional para guardar la matriz encapsulada. Otra forma es copiar el código de clasificación en cada función sobrecargada. La función sort () en la clase java.util.Arrays en la API oficial utiliza este método, que se puede ver en el código fuente de la clase de matrices. public static void sort (int [] input) {Integer [] t = new Integer [input.length]; for (int i = 0; i <input.length; i ++) {t [i] = input [i]; // encapsulation} Quicksort (t, 0, t.length); // clasificación para (int i = 0; i <input.length; i ++) {input [i] = t [i]; // uncapsulación de la función de sobrecarla entrada) {double [] t = new Double [input.length]; for (int i = 0; i <input.length; i ++) {t [i] = input [i]; } Quicksort (t, 0, t.length); for (int i = 0; i <input.length; i ++) {input [i] = t [i]; }} // Función de sobrecarga de byte [] array public static void sort (byte [] input) {byte [] t = new byte [input.length]; for (int i = 0; i <input.length; i ++) {t [i] = input [i]; } Quicksort (t, 0, t.length); for (int i = 0; i <input.length; i ++) {t [i] = input [i]; } Quicksort (t, 0, t.length); para (int i = 0; i <input.length); input.length; i ++) {input [i] = t [i]; }} // Función de sobrecarga corta [] Public static void sort (short [] input) {short [] t = new Short [input.length]; for (int i = 0; i <input.length; i ++) {t [i] = input [i]; } Quicksort (t, 0, t.length); for (int i = 0; i <input.length; i ++) {input [i] = t [i]; }} // Función de sobrecarga corta [] Public static void sort (char [] input) {carácter [] t = nuevo carácter [input.length]; for (int i = 0; i <input.length; i ++) {t [i] = input [i]; } Quicksort (t, 0, t.length); for (int i = 0; i <input.length; i ++) {input [i] = t [i]; }} // Función de sobrecarga de Float [] Array public static void sort (float [] input) {float [] t = new float [input.length]; for (int i = 0; i <input.length; i ++) {t [i] = input [i]; } Quicksort (t, 0, t.length); for (int i = 0; i <input.length; i ++) {input [i] = t [i]; }} // La función principal para probar públicamente estática void main (string [] args) {// producir una matriz int [] compuesta de números aleatorios para probar int len = 10; int [] input = new int [len]; Random r = new Random (); System.out.print ("int [] antes de clasificar:"); for (int i = 0; i <input.length; i ++) {input [i] = R.NextInt (10*len); System.out.print (entrada [i] + ""); } System.out.println (); System.out.print ("int [] después de clasificar:"); ordenar (entrada); for (int i: input) {System.out.print (i + ""); } System.out.println (); // Generar una matriz de cadenas para probar la cadena [] s = nueva cadena [] {"b", "a", "e", "d", "f", "c"}; System.out.print ("String [] antes de clasificar:"); for (int i = 0; i <s.length; i ++) {system.out.print (s [i]+""); } System.out.println (); System.out.print ("String [] después de clasificar:"); ordenar (s); for (int i = 0; i <s.length; i ++) {system.out.print (s [i]+""); } System.out.println (); // Generar una lista de cadenas para probar la lista <String> l = new LinkedList <String> (); s = nueva cadena [] {"b", "a", "e", "d", "f", "c"}; System.out.print ("LinkedList <String> antes de clasificar:"); para (int j = 0; j <s.length; j ++) {l.add (s [j]); System.out.print (s [j] + ""); } System.out.println (); ordenar (l); System.out.print ("LinkedList <String> después de clasificar:"); for (string ts: l) {system.out.print (ts + ""); } System.out.println (); }}Ejecute la prueba de función principal y desde la salida, puede ver que la clase QuickSort funciona normalmente:
int [] antes de clasificar: 65 48 92 26 3 8 59 21 16 45Int [] Después de clasificar: 3 8 16 21 26 45 48 59 65 92String [] Antes de clasificar: Baedfc String [] Después de clasificar: ABCDEF LinkedList <String> Antes de clasificar: Baedfc LinkedList <String> después de clasificar: ABCDEF