Clasificación de selección simple: (seleccione el valor mínimo, colóquelo primero, y luego el primer bit avanza hacia atrás, por lo que el bit) se compara con cada uno después del siguiente, cada vez que el bit más pequeño se remonta y el primer bit está hacia atrás Promocione (es decir, el primer dígito que se acaba de seleccionar es el valor mínimo, ya no participa en la comparación, el número de comparaciones se reduce en 1)
Complejidad: el número de operaciones requeridas para realizar el movimiento de registro es 0-3 (N-1). / 2. La complejidad del tiempo total es O (N2);
Complejidad espacial o (1)
Mejora del algoritmo: cada vez que se compara, es poner el valor más pequeño en primer lugar, para que pueda compararlo hasta el final, encontrar el valor mínimo y ponerlo directamente en primer lugar, eliminando las operaciones de conmutación y móvil sin sentido. También puede cambiar la dirección, comparar el último bit con cada anterior y hacer el valor máximo de fondo cada vez, y empujar el último bit hacia adelante.
Código fuente de Java:
La copia del código es la siguiente:
Public static void selectsort (fecha [] días) {
int min;
Fecha temperatura;
para (int i = 0; i <days.length; i ++) {
min = i;
para (int j = min+1; j <days.length; j ++) {
if (días [min] .compare (días [j])> 0) {
min = j;
}
}
if (min! = i) {
temp = días [i];
días [i] = días [min];
días [min] = temp;
}
}
}
Fecha de clase {
int año, mes, día;
Fecha (int y, int m, int d) {
año = y;
mes = m;
día = D;
}
public int Compare (fecha de fecha) {
Año de regreso> Fecha.
: mes> fecha. ¿Month?
: día> date.day?
}
public void print () {
System.out.println (año + "" + mes + "" + día);
}
}
Orden de selección simple:
El tipo de selección simple es similar a la clasificación de burbujas (clasificación de burbujas). La única diferencia es que la clasificación de burbujas cambia la ubicación del elemento cada vez que encuentra que es más pequeño (o mayor) que el valor actual, mientras que la clasificación de selección simple es seleccionar el mayor valor en los elementos restantes e intercambiar datos en el posición actual.
Por ejemplo, para el conjunto de elementos R = {37, 40, 38, 42, 461, 5, 7, 9, 12}
En el primer orden: 37 se intercambia directamente con 5, formando una nueva secuencia R1 = {5,40,38,42,461,37,7,9,12}
En el segundo orden: 40 se intercambia directamente con 7, formando una nueva secuencia R2 = {5,7,38,42,461,37,40,9,12}
Y así sucesivamente hasta el último elemento (nota: en el segundo orden, 38 es menor que 42, pero no intercambian datos).
Aquí hay una versión de implementación de Java que simplemente selecciona la clasificación:
La copia del código es la siguiente:
public static void selectionsort (int [] data) {
if (data == null || data.length <= 1)
devolver;
int i, j, valor, minpos, len = data.length;
int externo = len - 1, tmp;
para (i = 0; i <exterior; i ++) {
valor = datos [i];
minpos = -1;
para (j = i+1; j <len; j ++) {
if (data [j] <valor) {
minpos = j;
valor = datos [j];
}
}
if (minpos! = -1) {
tmp = data [i];
datos [i] = valor;
datos [minPOS] = tmp;
}
// para (int k = 0; k <len; k ++) {
// system.out.print (datos [k] + ",");
//}
// System.out.println ();
}
}
public static void main (string [] args) {
int [] coll = {
37, 40, 38, 42, 461, 5, 7, 9, 12
};
selectionsort (coll);
para (int i = 0; i <coll.length; i ++) {
System.out.print (coll [i] + ",");
}
}
Orden de selección de árboles
El algoritmo de clasificación de selección de árboles es un algoritmo típico que intercambia espacio por el tiempo en comparación con la clasificación de selección simple. La idea es tratar los n elementos ordenados, construir números relativamente pequeños (n+1)/2 y luego construir números relativamente pequeños [n+1]/4 hasta que solo haya un elemento. Construido en un árbol completamente binario.
Al clasificar, el elemento es el más pequeño.
Aquí hay una versión de implementación de Java de la clasificación de la selección de árboles:
La copia del código es la siguiente:
public static void treeSelectionsort (int [] datos) {
if (data == null || data.length <= 1)
devolver;
int len = data.length, low = 0, i, j;
// Agregar espacio auxiliar
int [] tmp = new int [2*len -1];
int tsize = tmp.length;
// construir un árbol
para (i = len-1, j = tmp.length-1; i> = 0; i-, j-) {
tmp [j] = data [i];
}
para (i = tsize -1; i> 0; i- = 2) {
tmp [(i-1)/2] = tmp [i]> tmp [i-1]?
}
//fin
// Eliminar el nodo mínimo.
while (bajo <len) {
datos [Low ++] = tmp [0];
para (j = tsize-1; tmp [j]! = tmp [0]; j--);
tmp [j] = integer.max_value;
while (j> 0) {
if (j%2 == 0) {// Si es un nodo correcto
tmp [(j-1)/2] = tmp [j]> tmp [j-1]? tmp [j-1]: tmp [j];
j = (j-1)/2;
} else {// Si es el nodo izquierdo
tmp [j/2] = tmp [j]> tmp [j+1]? tmp [j+1]: tmp [j];
j = j/2;
}
}
}
}
Al construir un árbol binario completo, se requiere espacio auxiliar 2*n -1 para una colección de n elementos.
Código:
La copia del código es la siguiente:
while (j> 0) {
if (j%2 == 0) {// Si es un nodo correcto
tmp [(j-1)/2] = tmp [j]> tmp [j-1]? tmp [j-1]: tmp [j];
j = (j-1)/2;
} else {// Si es el nodo izquierdo
tmp [j/2] = tmp [j]> tmp [j+1]? tmp [j+1]: tmp [j];
j = j/2;
}
}
Luego implementa la construcción recursiva del valor mínimo en el nuevo conjunto.