Este artículo describe la operación de selección de tiempo lineal implementada por Java basada en el algoritmo de partición y conquista. Compártelo para su referencia, como sigue:
Problema de selección de tiempo lineal: dados n elementos y un entero k, 1≤k≤n, es necesario averiguar el elemento más pequeño de estos elementos n (el conjunto lineal dado aquí está desordenado).
Selección lineal dividida al azar
El método de división aleatoria de selección de tiempo lineal puede imitar el diseño del algoritmo de clasificación rápida aleatoria. La idea básica es dividir recursivamente la matriz de entrada. A diferencia de la clasificación rápida, solo procesa recursivamente uno de los subarrays divididos.
Explicación del programa: Use una función aleatoria para generar un punto de referencia de división, divida la matriz A [P: R] en dos subarrayes A [P: I] y A [I+1: R], de modo que cada elemento en A [P: I] no sea mayor que cada elemento en un [i+1: R]. Entonces "j = i-p+1" calcula el número de elementos j en a [p: i]. Si k <= j, entonces el elemento más pequeño K-th en a [P: R] está en el sub-Array A [P: I], y si K> J, el elemento más pequeño K está en el sub-Array A [i+1: R]. Nota: Dado que se sabe que los elementos en el sub-array A [P: I] son todos más pequeños que el elemento pequeño K -th que se encuentra, el elemento pequeño K -th en un [P: R] que se encuentra es el elemento pequeño K-Th en A [i+1: R].
En el peor de los casos, por ejemplo: cuando siempre se encuentra el elemento más pequeño, siempre se divide en el elemento más grande, que es la complejidad del tiempo de O (n^2) . Sin embargo, la complejidad del tiempo promedio está relacionada linealmente con N, que es o (n)
paquete matemático; import java.util.scanner; import java.util.random; public class RandomSelect {public static void swap (int x, int y) {int temp = x; x = y; y = temp; } public int Random (int x, int y) {Random Random = new Random (); int num = random.nextint (y)%(y - x + 1) + x; num de devolución; } public int Partition (int [] list, int low, int high) {int tmp = list [low]; // El primero de la matriz es el eje central, mientras que (bajo <alto) {while (bajo <high && list [high]> tmp) {high--; } list [Low] = list [alto]; // Los registros más pequeños que el eje central se mueven al extremo bajo, mientras que (bajo <high && list [bajo] <tmp) {Low ++; } list [high] = list [Low]; // Los registros más grandes que el eje central se mueven a la lista de gama alta} [Low] = tmp; // Los registros más grandes que el eje central se devuelven bajo; // Regrese a la posición del eje central} public int aleationPartition (int [] matrices, int izquierdo, int right) {int i = aleator (izquierda, derecha); intercambio (matrices [i], matrices [izquierda]); Partición de retorno (matrices, izquierda, derecha); } public int aleationSelect (int [] matrices, int izquierdo, int right, int k) {if (left == right) {return matrices [izquierda]; } int i = aleationPartition (matrices, izquierda, derecha); int j = i - izquierda + 1; if (k <= j) {return aleationSelect (matrices, izquierda, i, k); } else {return RandomizeSelect (matrices, i+1, derecha, kj); }} public static void main (string args []) {System.out.println ("Wulin.com Test Resultado:"); int [] a = {7,5,3,4,8,6,9,1,2}; para (int i = 0; i <9; i ++) {System.out.print (a [i]+""); } System.out.println (); RandomSelect r = new RandomSelect (); System.out.println ("¿Qué elemento más pequeño quieres consultar en la matriz?"); @SupessWarnings ("recurso") escáner sc = new Scanner (System.in); int m = sc.nextInt (); int n = randomizedSelect (a, 0,8, m); System.out.println ("el" th "en esta matriz" + m + "El elemento más pequeño es:" + n); }}Resultados de ejecución:
Para obtener más información sobre los algoritmos de Java, los lectores interesados en este sitio pueden ver los temas: "Estructura de datos Java y tutorial de algoritmo", "Resumen de las puntas de nodo de operación de Java DOM", "Resumen de Java Archivo y TIPS de operación de directorio" y "Summary of Java Cache Operation Tips" TIPS ""
Espero que este artículo sea útil para la programación Java de todos.