estabilidad (estabilidad)
Un algoritmo de clasificación es estable, es decir, cuando hay dos registros iguales de las claves R y S, y R aparece antes de S en la lista original, R también aparecerá antes de S en la lista ordenada.
Clasificación del algoritmo de clasificación.
Los más comunes incluyen inserción (clasificación por inserción/clasificación Hill), intercambio (clasificación por burbuja/clasificación rápida), selección (clasificación por selección), fusión (clasificación por combinación), etc.
1. Ordenación por inserción
La clasificación por inserción funciona construyendo una secuencia ordenada para datos no clasificados, escanea de atrás hacia adelante en la secuencia ordenada para encontrar la posición correspondiente e insertarla. En la implementación de la ordenación por inserción, generalmente se usa la ordenación in situ (es decir, la ordenación que solo usa O (1) espacio adicional. Por lo tanto, durante el proceso de escaneo de atrás hacia adelante, es necesario cambiar el orden de forma repetida y gradual). elementos ordenados hacia atrás, proporcionando espacio de inserción para el último elemento.
En términos generales, la ordenación por inserción se implementa en matrices mediante el uso in situ. El algoritmo específico se describe a continuación:
A partir del primer elemento, se puede considerar que los elementos han sido ordenados.
Obtenga el siguiente elemento y escanee de atrás hacia adelante en la secuencia ordenada de elementos.
Si el elemento (ordenado) es más grande que el nuevo elemento, mueva el elemento a la siguiente posición.
Repita el paso 3 hasta encontrar una posición donde el elemento ordenado sea menor o igual que el nuevo elemento.
Después de insertar el nuevo elemento en esa posición.
Repita los pasos 2 a 5.
Copie el código de código de la siguiente manera:
InsertionSort de vacío estático público (int [] datos) {
para (int índice = 1; índice < datos.longitud; índice ++) {
clave int = datos[índice];
posición int = índice;
// desplaza los valores más grandes hacia la derecha
while (posición > 0 && datos[posición - 1] > tecla) {
datos[posición] = datos[posición - 1];
posición--;
}
datos[posición] = clave;
}
}
2. Clasificación de colinas
Shell Sort es un tipo de ordenación por inserción. Es una mejora del algoritmo de clasificación por inserción directa. Este método también se denomina clasificación incremental reducida, porque DL. Shell lleva el nombre de su propuesta en 1959.
La clasificación Hill propone un método mejorado basado en las dos propiedades siguientes de la clasificación por inserción:
La clasificación por inserción es muy eficiente cuando se opera con datos casi ordenados, es decir, puede lograr la eficiencia de la clasificación lineal.
Pero la ordenación por inserción es generalmente ineficiente porque la ordenación por inserción solo puede mover datos un bit a la vez.
Copie el código de código de la siguiente manera:
static <E extiende Comparable<? super E>> void shellSort(List<E> a) {
int h = 1;
while (h < a.size()/3) h = h*3 + 1; // <O(n^(3/2)) por Knuth,1973>: 1, 4, 13, 40, 121,. ..
para (; h >= 1; h /= 3)
para (int i = h; i < a.size(); i++)
for (int j = i; j >= h && a.get(j).compareTo(a.get(jh)) < 0; j-=h)
Colecciones.swap(a, j, jh);
}
3. Clasificación de burbujas
Bubble Sort (Bubble Sort, traducido de Taiwán como: Bubble Sort o Bubble Sort) es un algoritmo de clasificación simple. Recorre repetidamente la secuencia a ordenar, comparando dos elementos a la vez e intercambiándolos si están en el orden incorrecto. El trabajo de visitar la matriz se repite hasta que no se necesitan más intercambios, lo que significa que la matriz ha sido ordenada. El nombre de este algoritmo proviene del hecho de que los elementos más pequeños "flotarán" lentamente hasta la parte superior de la matriz mediante el intercambio.
El algoritmo de clasificación de burbujas funciona de la siguiente manera:
Compara elementos adyacentes y, si el primero es mayor que el segundo, intercámbialos ambos.
Haga lo mismo para cada par de elementos adyacentes, comenzando con el primer par y terminando con el último par, momento en el que el último elemento debería ser el número más grande.
Repita los pasos anteriores para todos los elementos excepto el último.
Siga repitiendo los pasos anteriores para cada vez menos elementos cada vez hasta que no queden pares de números para comparar.
Copie el código de código de la siguiente manera:
bubbleSort público estático vacío (int [] datos) {
temperatura interna = 0;
para (int i = datos.longitud - 1; i > 0; --i) {
booleano isSort = falso;
para (int j = 0; j < i; ++j) {
si (datos[j + 1] <datos[j]) {
temperatura = datos[j];
datos[j] = datos[j + 1];
datos[j + 1] = temperatura;
isOrdenar = verdadero;
}
}
// Si se produce un intercambio en un bucle interno, continúa la comparación; si no se produce ningún intercambio en un bucle interno, se considera ordenado.
si (!isOrt)
romper;
}
}
4. Clasificación rápida
Quicksort es una mejora de la clasificación de burbujas. Propuesto por CAR Hoare en 1962. Su idea básica es dividir los datos que se van a ordenar en dos partes independientes mediante una clasificación. Todos los datos de una parte son más pequeños que todos los datos de la otra parte y luego utilizar este método para separar rápidamente las dos partes de los datos. Clasificación, todo el proceso de clasificación se puede realizar de forma recursiva, de modo que todos los datos se conviertan en una secuencia ordenada.
La clasificación rápida utiliza la estrategia de dividir y conquistar para dividir una lista en dos sublistas.
Los pasos son:
Seleccionar un elemento de la secuencia se llama "pivote".
Reordene la matriz para que todos los elementos más pequeños que el valor base se coloquen delante de la base y todos los elementos más grandes que el valor base se coloquen detrás de la base (el mismo número puede ir a cualquier lado). Una vez que sale esta partición, la base está en el medio de la secuencia. Esto se llama operación de partición.
Ordene recursivamente el subconjunto de elementos menores que el valor base y el subconjunto de elementos mayores que el valor base.
Copie el código de código de la siguiente manera:
/*
* implementos más eficientes para clasificación rápida <br />
* use el valor mediano izquierdo, central y derecho (@ver #median()) para el pivote, y
* el bucle interno más eficiente para el núcleo del algoritmo.
*/
clasificación rápida de clase pública {
público estático final int CUTOFF = 11;
/**
* algoritmo de clasificación rápida <br />
*
* @param ofrece una variedad de elementos comparables <br />.
*/
public static <T extiende Comparable<? super T>> void quicksort(T[] arr) {
clasificación rápida(arr, 0, longitud.arr - 1);
}
/**
*obtener la mediana de la izquierda, centro y derecha <br />.
* ordene estos y oculte el pivote colocándolo al final de la matriz <br />.
*
* @param ofrece una variedad de elementos comparables <br />.
* @param dejó el índice más a la izquierda del subarreglo <br />.
* @param a la derecha el índice más a la derecha del subarreglo.<br />
* @retorno T
*/
public static <T extiende Comparable<? super T>> T mediana(T[] arr, int izquierda, int derecha) {
int centro = (izquierda + derecha) / 2;
si (arr[izquierda].compareTo(arr[centro]) > 0)
swapRef(arr, izquierda, centro);
si (arr[izquierda].compareTo(arr[derecha]) > 0)
swapRef(arr, izquierda, derecha);
si (arr[centro].compareTo(arr[derecha]) > 0)
swapRef(arr, centro, derecha);
swapRef(arr, centro, derecha - 1);
retorno arr[derecha - 1];
}
/**
* método interno para ordenar la matriz con algoritmo de clasificación rápida <br />
*
* @param ofrece una variedad de elementos comparables <br />.
* @param dejó el índice más a la izquierda del subarreglo <br />.
* @param a la derecha del índice más a la derecha del subarreglo <br />.
*/
privado estático <T extiende Comparable<? super T>> void quickSort(T[] arr, int izquierda, int derecha) {
if (izquierda + CORTE <= derecha) {
// encuentra el pivote
Pivote T = mediana(arr, izquierda, derecha);
//comenzar a particionar
int i = izquierda, j = derecha - 1;
para (;;) {
mientras (arr[++i].compareTo(pivote) < 0);
mientras (arr[--j].compareTo(pivote) > 0);
si (yo <j)
swapRef(arr, i, j);
demás
romper;
}
// cambia la referencia de pivote a la colección pequeña.
swapRef(arr, i, derecha - 1);
quickSort(arr, left, i - 1); // ordena la colección pequeña.
quickSort(arr, i + 1, right); // ordena la colección grande.
} demás {
// si el número total es menor que CUTOFF usamos ordenación por inserción
// en su lugar (porque es mucho más eficiente).
Ordenar(arr, inserción izquierda, derecha);
}
}
/**
* método para intercambiar referencias en una matriz.<br />
*
* @param organiza una serie de objetos <br />.
* @param idx1 el índice del primer elemento <br />
* @param idx2 el índice del segundo elemento <br />
*/
public static <T> void swapRef(T[] arr, int idx1, int idx2) {
T tmp = arr[idx1];
arreglo[idx1] = arreglo[idx2];
arr[idx2] = tmp;
}
/**
* método para ordenar un subarreglo de principio a fin con ordenación por inserción
* algoritmo.
*
* @param ofrece una variedad de elementos comparables <br />.
* @param inicia la posición inicial <br />
* @param finaliza la posición final <br />
*/
public static <T extiende Comparable<? super T>> void insertionSort(T[] arr, int start, int end) {
ent i;
for (int j = inicio + 1; j <= fin; j++) {
T tmp = arreglo[j];
for (i = j; i > inicio && tmp.compareTo(arr[i - 1]) < 0; i--) {
arreglo[i] = arreglo[i - 1];
}
arreglo[i] = tmp;
}
}
printArray vacío estático privado (Entero [] c) {
para (int i = 0; i < c.length; i++)
System.out.print(c[i] + ",");
System.out.println();
}
público estático vacío principal (String [] argumentos) {
Datos enteros [] = {10, 4, 9, 23, 1, 45, 27, 5, 2};
System.out.println("ordenación de burbujas...");
imprimirArray(datos);
clasificación rápida (datos);
imprimirArray(datos);
}
}
5. Clasificación de selección
La clasificación por selección es un algoritmo de clasificación simple e intuitivo. Así es como funciona. Primero, busque el elemento más pequeño (grande) en la secuencia sin clasificar y guárdelo al comienzo de la secuencia ordenada. Luego, continúe buscando el elemento más pequeño (grande) de los elementos restantes sin clasificar y luego colóquelo al final de la secuencia. secuencia ordenada. Y así sucesivamente hasta que todos los elementos estén ordenados.
Debido a que cada proceso de determinación de elementos tendrá un subproceso de selección del valor mínimo, la gente lo llama vívidamente clasificación por selección.
Por ejemplo, en la secuencia 5 8 5 2 9, sabemos que el primer elemento 5 se intercambiará con 2 en la primera pasada, luego se destruirá el orden relativo de los dos 5 en la secuencia original, por lo que la clasificación por selección es. no estable.
Copie el código de código de la siguiente manera:
selectSort público estático vacío (int [] datos) {
int índicemínimo = 0;
temperatura interna = 0;
para (int i = 0; i < data.length; i++) {
minIndex = i; // El índice mínimo de matriz de datos del área desordenada
for (int j = i + 1; j < data.length; j++) { // Encuentra los datos más pequeños en el área desordenada y guarda su subíndice de matriz
si (datos[j] <datos[minIndex]) {
índicemínimo = j;
}
}
if (minIndex != i) { // Si la posición mínima del área desordenada no es el primer dato predeterminado, intercámbielo.
temperatura = datos[i];
datos[i] = datos[minIndex];
datos[minIndex] = temporal;
}
}
}
6. Combinar clasificación
Merge sort es un algoritmo de clasificación eficaz basado en operaciones de fusión. Este algoritmo es una aplicación muy típica que utiliza el método divide y vencerás (Divide y vencerás).
El proceso de operación de fusión es el siguiente:
Solicite espacio para que su tamaño sea la suma de las dos secuencias ordenadas. Este espacio se utiliza para almacenar la secuencia fusionada.
Establezca dos punteros, las posiciones iniciales son las posiciones iniciales de las dos secuencias ordenadas.
Compare los elementos señalados por los dos punteros, seleccione el elemento relativamente pequeño, colóquelo en el espacio de combinación y mueva el puntero a la siguiente posición.
Repita el paso 3 hasta que un puntero llegue al final de la secuencia.
Copia todos los elementos restantes de la otra secuencia directamente al final de la secuencia fusionada.
Copie el código de código de la siguiente manera:
public static int[] mergeSort(int[] arr) {//Fusionar ordenación - recursividad
if (longitud del arreglo == 1) {
volver llegar;
}
int mitad = longitud del arreglo / 2;
int[] arr1 = nuevo int[mitad];
int[] arr2 = nuevo int[arr.length - half];
System.arraycopy(arr, 0, arr1, 0, arr1.length);
System.arraycopy(arr, half, arr2, 0, arr2.length);
arr1 = fusionarOrdenar(arr1);
arr2 = fusionarOrdenar(arr2);
devolver mergeSortSub(arr1, arr2);
}
private static int[] mergeSortSub(int[] arr1, int[] arr2) {// Combinar subrutina de clasificación
int[] resultado = nuevo int[arr1.length + arr2.length];
int yo = 0;
int j = 0;
int k = 0;
mientras (verdadero) {
si (arr1[i] <arr2[j]) {
resultado[k] = arreglo1[i];
si (++i > arr1.longitud - 1) {
romper;
}
} demás {
resultado[k] = arr2[j];
si (++j > arr2.longitud - 1) {
romper;
}
}
k++;
}
para (; i < arr1.length; i++) {
resultado[++k] = arr1[i];
}
para (; j < arr2.length; j++) {
resultado[++k] = arr2[j];
}
resultado de devolución;
}
Código completo (excepto QuickSort)
Copie el código de código de la siguiente manera:
paquete com.clzhang.sample.thinking;
importar java.util.*;
/**
* Implementación Java de varios algoritmos de clasificación comunes.
* @autor acer
*
*/
clase pública Orden común {
/**
* El algoritmo específico de ordenación por inserción se describe a continuación:
* 1. A partir del primer elemento, se puede considerar que el elemento ha sido ordenado.
* 2. Saque el siguiente elemento y escanee de atrás hacia adelante en la secuencia de elementos ordenados
* 3. Si el elemento (ordenado) es más grande que el nuevo elemento, mueva el elemento a la siguiente posición
* 4. Repita el paso 3 hasta encontrar la posición donde el elemento ordenado es menor o igual que el nuevo elemento
* 5. Después de insertar el nuevo elemento en esta posición
* 6. Repita los pasos 2 ~ 5
*/
InsertionSort de vacío estático público (int [] datos) {
para (int índice = 1; índice < datos.longitud; índice ++) {
clave int = datos[índice];
posición int = índice;
// desplaza los valores más grandes hacia la derecha
while (posición > 0 && datos[posición - 1] > tecla) {
datos[posición] = datos[posición - 1];
posición--;
}
datos[posición] = clave;
}
}
/**
* Clasificación Hill, consulte Wikipedia para obtener ideas de implementación de algoritmos adecuados para una gran cantidad de operaciones de clasificación;
*/
static <E extiende Comparable<? super E>> void shellSort(List<E> a) {
int h = 1;
while (h < a.size()/3) h = h*3 + 1; // <O(n^(3/2)) por Knuth,1973>: 1, 4, 13, 40, 121,. ..
para (; h >= 1; h /= 3)
para (int i = h; i < a.size(); i++)
para (int j = i; j >= h && a.get(j).compareTo(a.get(jh)) < 0; j-=h)
Colecciones.swap(a, j, jh);
}
/**
* El funcionamiento del algoritmo de clasificación de burbujas es el siguiente:
* 1. Compara elementos adyacentes. Si el primero es más grande que el segundo, cámbialos ambos.
* 2. Haz el mismo trabajo para cada par de elementos adyacentes, desde el primer par al principio hasta el último par al final. En este punto, el último elemento debería ser el número más grande.
* 3. Repita los pasos anteriores para todos los elementos excepto el último.
* 4. Continúe repitiendo los pasos anteriores para cada vez menos elementos cada vez hasta que no haya pares de números para comparar. [1]
*/
bubbleSort público estático vacío (int [] datos) {
temperatura interna = 0;
para (int i = datos.longitud - 1; i > 0; --i) {
booleano isSort = falso;
para (int j = 0; j < i; ++j) {
si (datos[j + 1] <datos[j]) {
temperatura = datos[j];
datos[j] = datos[j + 1];
datos[j + 1] = temperatura;
isOrdenar = verdadero;
}
}
// Si se produce un intercambio en un bucle interno, continúa la comparación; si no se produce ningún intercambio en un bucle interno, se considera ordenado.
si (!isOrt)
romper;
}
}
/**
* La idea básica de la clasificación por selección es:
* 1. Durante el proceso de recorrer la matriz, si i representa el número de secuencia actual que debe ordenarse, debe encontrar el valor mínimo entre los [i+1...n-1] restantes.
* 2. Luego intercambie el valor mínimo encontrado con el valor señalado por i.
* Debido a que cada proceso de determinación de elementos tendrá un subproceso de selección del valor mínimo, la gente lo llama vívidamente clasificación por selección.
* @param datos
*/
selectSort público estático vacío (int [] datos) {
int índice mínimo = 0;
temperatura interna = 0;
para (int i = 0; i < data.length; i++) {
minIndex = i; // El índice mínimo de matriz de datos del área desordenada
for (int j = i + 1; j < data.length; j++) { // Encuentra los datos más pequeños en el área desordenada y guarda su subíndice de matriz
si (datos[j] <datos[minIndex]) {
índicemínimo = j;
}
}
if (minIndex != i) { // Si la posición mínima del área desordenada no es el primer dato predeterminado, cámbielo.
temperatura = datos[i];
datos[i] = datos[minIndex];
datos[minIndex] = temp;
}
}
}
/**
* El proceso de operación de fusión es el siguiente:
* 1. Solicite espacio para que su tamaño sea la suma de las dos secuencias ordenadas. Este espacio se utiliza para almacenar la secuencia fusionada.
* 2. Establezca dos punteros, las posiciones iniciales son las posiciones iniciales de las dos secuencias ordenadas.
* 3. Compare los elementos señalados por los dos punteros, seleccione el elemento relativamente pequeño y colóquelo en el espacio de combinación, y mueva el puntero a la siguiente posición
* 4. Repita el paso 3 hasta que un puntero llegue al final de la secuencia.
* 5. Copie todos los elementos restantes de la otra secuencia directamente al final de la secuencia fusionada
*/
public static int[] mergeSort(int[] arr) {//Fusionar ordenación - recursividad
if (longitud del arreglo == 1) {
volver llegar;
}
int mitad = longitud del arreglo / 2;
int[] arr1 = nuevo int[mitad];
int[] arr2 = nuevo int[arr.length - half];
System.arraycopy(arr, 0, arr1, 0, arr1.length);
System.arraycopy(arr, half, arr2, 0, arr2.length);
arr1 = fusionarOrdenar(arr1);
arr2 = fusionarOrdenar(arr2);
devolver mergeSortSub(arr1, arr2);
}
private static int[] mergeSortSub(int[] arr1, int[] arr2) {// Combinar subrutina de clasificación
int[] resultado = nuevo int[arr1.length + arr2.length];
int yo = 0;
int j = 0;
int k = 0;
mientras (verdadero) {
si (arr1[i] <arr2[j]) {
resultado[k] = arreglo1[i];
si (++i > arr1.longitud - 1) {
romper;
}
} demás {
resultado[k] = arr2[j];
si (++j > arr2.longitud - 1) {
romper;
}
}
k++;
}
para (; i < arr1.length; i++) {
resultado[++k] = arr1[i];
}
para (; j < arr2.length; j++) {
resultado[++k] = arr2[j];
}
resultado de devolución;
}
printArray vacío estático privado (int [] c) {
para (int i = 0; i < c.length; i++)
System.out.print(c[i] + ",");
System.out.println();
}
principal vacío estático público (cadena [] args) {
int[] datos = {10,4,9,23,1,45,27,5,2};
System.out.println("ordenación de burbujas...");
int[] a = datos.clon();
imprimirArray(a);
ordenación de burbujas (a);
imprimirArray(a);
System.out.println("seleccionarOrdenar...");
int[] b = datos.clon();
imprimirArray(b);
seleccionarOrdenar(b);
imprimirArray(b);
System.out.println("inserciónOrdenar...");
int[] c = datos.clon();
imprimirArray(c);
ordenación de inserción (c);
imprimirArray(c);
System.out.println("shellSort...");
Lista<Integer> lista = nueva ArrayList<Integer>();
para(int i=0;i<data.length;i++)
lista.add(datos[i]);
System.out.println(lista);
shellOrdenar(lista);
System.out.println(lista);
System.out.println("mergeSort...");
int[] d = datos.clon();
imprimirArray(d);
printArray(mergeSort(d));
}
}