a) Principio : cada vez, seleccione el elemento más pequeño de los registros que se clasificarán y colóquelo en el orden al final de la secuencia ordenada hasta que se ordenen todos los registros. Es decir, cada viaje se selecciona como el registro I-Th en la secuencia ordenada entre los registros N-I+1 (i = 1, 2, ... N-1). Los algoritmos basados en esta idea incluyen principalmente clasificación de selección simple, clasificación de selección de árboles y clasificación de montón. (Esta es solo una clasificación de selección simple común)
b) la idea básica de la selección simple de clasificación : dada una matriz: int [] arr = {n datos en it}; La primera vez que clasifica, seleccione los datos más pequeños en los datos que se ordenarán arr [1] ~ arr [n], e intercambie con arr [1]; La segunda vez, seleccione los datos más pequeños en los datos que se ordenarán arr [2] ~ arr [n], e intercambílos con r [2]; y así sucesivamente, seleccione los datos más pequeños en los datos que se ordenarán arr [i] ~ arr [n], e intercambie con r [i] hasta que se complete toda la clasificación.
c) Ejemplo : Array int [] arr = {5,2,8,4,9,1};
-------------------------------------------------------
Primer orden: Datos originales: 528491
Datos mínimos 1, poner 1 primero, es decir, 1 y 5 posiciones de intercambio,
Resultado de clasificación: 128495
-------------------------------------------------------
Segundo orden:
Se compara los datos fuera de 1 {28495}, 2 es el más pequeño,
Resultado de clasificación: 128495
-------------------------------------------------------
El tercer orden:
Se comparan los datos distintos de 1 y 2 {8495}, 4 son mínimos, 8 y 4 se intercambian
Resultado de clasificación: 124895
-------------------------------------------------------
El cuarto orden:
Se comparan otros datos que no se comparan 1, 2, 4 {895}, 5 son mínimos, 8 y 5 se intercambian
Resultado de clasificación: 124598
-------------------------------------------------------
El quinto orden:
Se comparan otros datos que no se comparan 1, 2, 4, 5, 8 son mínimos, 8 y 9 se intercambian
Resultado de clasificación: 124589
-------------------------------------------------------
Nota: El método para obtener el número más pequeño en cada pedido: para que el bucle compare, defina una tercera temperatura variable. Primero, compare los dos primeros números, coloque el número más pequeño en TEMP y luego use TEMP para comparar con los datos restantes. Si aparecen datos más pequeños que TEMP, úselo en lugar de los datos originales en temp. Para obtener más detalles, referirse a los ejemplos de código a continuación, creo que ha aprendido la declaración para bucle antes de aprender a clasificar. De esta manera, será particularmente fácil de entender aquí.
Ejemplo de código:
// Seleccione Ordenar la clase pública selectionsort {public static void main (string [] args) {int [] arr = {1,3,2,45,65,33,12}; System.out.println ("antes de intercambio:"); for (int num: arr) {system.out.print (num+""); } // Seleccione la optimización de la clasificación para (int i = 0; i <arr.length - 1; i ++) {// ordene el orden i -th orden int k = i; for (int j = k+1; j <arr.length; j ++) {// Seleccione el registro más pequeño if (arr [j] <arr [k]) {k = j; // Tenga en cuenta la ubicación del valor mínimo encontrado hasta ahora}} // Después del final del bucle interno, es decir, después de encontrar el número mínimo de este bucle, luego intercambiar if (i! = K) {// intercambie a [i] y a [k] int temp = arr [i]; arr [i] = arr [k]; arr [k] = temp; }} System.out.println (); System.out.println ("después de intercambio:"); for (int num: arr) {system.out.print (num+""); }}}Captura de pantalla del resultado de ejecución:
Seleccione la complejidad del tiempo de la clasificación: el número de comparaciones de tipos de selección simple no tiene nada que ver con la clasificación inicial de la secuencia. Suponiendo que la secuencia a ordenar tiene n elementos, el número de comparaciones siempre será N (N-1)/2. El número de movimientos está relacionado con la clasificación inicial de la secuencia. Cuando la secuencia es positiva, el número de movimientos es el menor, que es 0. Cuando la secuencia se secuencia inversamente, la mayoría de los movimientos son 3n (N-1)/2.
Entonces, en resumen, la complejidad del tiempo de la clasificación simple es O (N2).