importar java.util.Random;
/**
* Clase de prueba de clasificación
*
* La clasificación de los algoritmos de clasificación es la siguiente: 1. Clasificación por inserción (clasificación por inserción directa, clasificación por media inserción, clasificación Hill 2. Clasificación por intercambio (clasificación por burbuja, clasificación rápida);
* 3. Clasificación por selección (clasificación por selección directa, clasificación en montón); 4. Clasificación por combinación; 5. Clasificación por base;
*
* Con respecto a la elección del método de clasificación: (1) Si n es pequeño (como n≤50), se puede utilizar la clasificación por inserción directa o selección directa.
* Cuando el tamaño del registro es pequeño, la clasificación por inserción directa es mejor; de lo contrario, debido a que la cantidad de registros movidos por selección directa es menor que la de la inserción directa, la clasificación por selección directa es mejor.
* (2) Si el estado inicial del archivo es básicamente en orden (refiriéndose al orden positivo), se debe utilizar la inserción directa, la burbuja o la clasificación rápida aleatoria;
* (3) Si n es grande, se debe utilizar un método de clasificación con una complejidad temporal de O (nlgn): clasificación rápida, clasificación en montón o clasificación por combinación.
*
*/
clase pública Ordenar {
/**
* Método para inicializar la matriz de prueba.
*
* @return una matriz inicializada
*/
público int[] crearArray() {
Aleatorio aleatorio = nuevo Aleatorio();
int[] matriz = nuevo int[10];
para (int i = 0; i < 10; i++) {
array[i] = random.nextInt(100) - random.nextInt(100); // Genera dos números aleatorios y rétalos para asegurar que haya números negativos en los números generados.
}
System.out.println("==========secuencia original==========");
imprimirMatriz(matriz);
matriz de retorno;
}
/**
* Imprime los elementos del array en la consola.
*
* @param fuente
*/
printArray vacío público (int [] datos) {
para (int i: datos) {
System.out.print(i + " ");
}
System.out.println();
}
/**
* Intercambiar las posiciones de los dos elementos especificados en la matriz.
*
* @param datos
* @paramx
* @param y
*/
intercambio vacío privado (int [] datos, int x, int y) {
int temperatura = datos[x];
datos[x] = datos[y];
datos[y] = temperatura;
}
/**
* Clasificación de burbujas----un tipo de clasificación de intercambio
* Método: compare dos elementos adyacentes e intercámbielos si es necesario. Una vez completado cada ciclo, el elemento más grande se clasifica en último lugar (como ordenar de pequeño a grande). El siguiente ciclo realizará operaciones similares en otros números.
* Rendimiento: número de comparaciones O(n^2),n^2/2 número de intercambios O(n^2),n^2/4;
*
* @param datos
* Matriz a ordenar
* @param tipo de clasificación
* Tipo de clasificación
* @devolver
*/
public void bubbleSort(int[] datos, String sortType) {
if (sortType.equals("asc")) { // Clasificación positiva, de pequeño a grande
// Número de rondas de comparación
para (int i = 1; i < data.length; i++) {
// Compara dos números adyacentes y el número mayor aparecerá.
for (int j = 0; j < datos.length - i; j++) {
si (datos[j] > datos[j + 1]) {
// Intercambia dos números adyacentes
intercambiar(datos, j, j + 1);
}
}
}
} else if (sortType.equals("desc")) { // Ordenar en orden inverso, de mayor a menor
// Número de rondas de comparación
para (int i = 1; i < data.length; i++) {
// Compara dos números adyacentes y el número mayor aparecerá.
for (int j = 0; j < datos.length - i; j++) {
si (datos[j] <datos[j + 1]) {
// Intercambia dos números adyacentes
intercambiar(datos, j, j + 1);
}
}
}
} demás {
System.out.println("¡El tipo de clasificación que ingresó es incorrecto!");
}
printArray(data);// Genera el valor de la matriz después de ordenar por burbujas
}
/**
* Método de clasificación por selección directa----un tipo de clasificación por selección
* Método: en cada pasada, se selecciona el elemento más pequeño (o más grande) de los elementos de datos a ordenar y el orden se coloca al final de la matriz ordenada hasta que todos los elementos de datos a ordenar estén organizados.
* Rendimiento: Número de comparaciones O(n^2),n^2/2
* Número de intercambios O(n),n
* El número de intercambios es mucho menor que el de la clasificación por burbujas. Dado que el intercambio requiere más tiempo de CPU que la comparación, la clasificación por selección es más rápida que la clasificación por burbujas.
* Pero cuando N es relativamente grande, domina el tiempo de CPU requerido para la comparación, por lo que el rendimiento en este momento no es muy diferente del tipo burbuja, pero sin duda es más rápido.
*
* @param datos
* Matriz a ordenar
* @param tipo de clasificación
* Tipo de clasificación
* @devolver
*
*/
public void selectSort(int[] datos, String sortType) {
if (sortType.equals("asc")) { // Clasificación positiva, de pequeño a grande
índice entero;
para (int i = 1; i < data.length; i++) {
índice = 0;
for (int j = 1; j <= datos.length - i; j++) {
if (datos[j] > datos[índice]) {
índice = j;
}
}
//Intercambia los dos números en la posición data.length-i e index (valor máximo)
swap(datos, datos.longitud - i, índice);
}
} else if (sortType.equals("desc")) { // Ordenar en orden inverso, de mayor a menor
índice entero;
para (int i = 1; i < data.length; i++) {
índice = 0;
for (int j = 1; j <= datos.length - i; j++) {
if (datos[j] <datos[índice]) {
índice = j;
}
}
//Intercambia los dos números en la posición data.length-i e index (valor máximo)
swap(datos, datos.longitud - i, índice);
}
} demás {
System.out.println("¡El tipo de clasificación que ingresó es incorrecto!");
}
printArray(data);// Genera el valor de la matriz después de la clasificación por selección directa
}
/**
*
* Orden de inserción
*
* Método: inserte un registro en una lista ordenada (posiblemente una lista vacía), obteniendo así una nueva lista ordenada con el número de registros aumentado en 1.
* Rendimiento: número de comparaciones O(n^2),n^2/4
* Número de copias O(n),n^2/4
* El número de comparaciones es promedio entre las dos primeras y la copia requiere menos tiempo de CPU que el intercambio, por lo que el rendimiento es más del doble que el de la clasificación por burbujas y más rápido que el de la clasificación por selección.
*
* @param datos
* Matriz a ordenar
* @param tipo de clasificación
* Tipo de clasificación
*/
public void insertSort(int[] datos, String sortType) {
if (sortType.equals("asc")) { // Clasificación positiva, de pequeño a grande
// Número de rondas de comparación
para (int i = 1; i < data.length; i++) {
// Asegúrate de que los primeros números i+1 estén ordenados
para (int j = 0; j < i; j++) {
si (datos[j] > datos[i]) {
// Intercambia los dos números en las posiciones j e i
intercambiar(datos, i, j);
}
}
}
} else if (sortType.equals("desc")) { // Ordenar en orden inverso, de mayor a menor
// Número de rondas de comparación
para (int i = 1; i < data.length; i++) {
// Asegúrate de que los primeros números i+1 estén ordenados
para (int j = 0; j < i; j++) {
si (datos[j] <datos[i]) {
// Intercambia los dos números en las posiciones j e i
intercambiar(datos, i, j);
}
}
}
} demás {
System.out.println("¡El tipo de clasificación que ingresó es incorrecto!");
}
printArray(data);// Genera el valor de la matriz después de la clasificación por inserción
}
/**
*
* Método para invertir una matriz
*
* @param datos
* matriz fuente
*/
reverso vacío público (int [] datos) {
int longitud = datos.longitud;
int temp = 0;//variable temporal
para (int i = 0; i < longitud / 2; i++) {
temperatura = datos[i];
datos[i] = datos[longitud - 1 - i];
datos[longitud - 1 - i] = temp;
}
printArray(data);//Envía el valor a la matriz convertida
}
/**
*
* Clasificación rápida
*
* La clasificación rápida utiliza la estrategia de dividir y conquistar para dividir una secuencia (lista) en dos subsecuencias (sublistas).
*
*Los pasos son:
* 1. Elija un elemento de la secuencia, llamado "pivote",
* 2. Reordene la secuencia de modo 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 (se puede colocar el mismo número en cualquier lado). Después de esta división, el dato se encuentra en su posición definitiva. Esto se llama operación de partición.
* 3. Ordene recursivamente el subarreglo de elementos menores que el valor base y el subarreglo de elementos mayores que el valor base.
*
* El caso inferior de recursividad es cuando el tamaño de la matriz es cero o uno, es decir, siempre ha estado ordenada. Aunque siga recurriendo, este algoritmo siempre terminará, porque en cada iteración (iteración), moverá al menos un elemento a su posición final.
*
* @param datos
* Matriz a ordenar
* @param bajo
* @param alto
* @ver SortTest#qsort(int[], int, int)
* @ver SortTest#qsort_desc(int[], int, int)
*
*/
public void quickSort(int[] datos, String sortType) {
if (sortType.equals("asc")) { // Clasificación positiva, de pequeño a grande
qsort_asc(datos, 0, datos.longitud - 1);
} else if (sortType.equals("desc")) { // Ordenar en orden inverso, de mayor a menor
qsort_desc(datos, 0, datos.longitud - 1);
} demás {
System.out.println("¡El tipo de clasificación que ingresó es incorrecto!");
}
}
/**
*
* Implementación específica de clasificación rápida, clasificación en orden correcto.
*
* @param datos
* @param bajo
* @param alto
*/
privado vacío qsort_asc (int datos [], int bajo, int alto) {
int i, j, x;
if (low < high) { // Esta condición se utiliza para finalizar la recursividad
yo = bajo;
j = alto;
x = datos[i];
mientras (yo < j) {
mientras (i < j && datos[j] > x) {
j--; // Encuentra el primer número menor que x de derecha a izquierda
}
si (yo <j) {
datos[i] = datos[j];
yo ++;
}
mientras (i < j && datos[i] < x) {
i++; // Encuentra el primer número mayor que x de izquierda a derecha
}
si (yo <j) {
datos[j] = datos[i];
j--;
}
}
datos[i] = x;
qsort_asc(datos, bajo, i - 1);
qsort_asc(datos, i + 1, alto);
}
}
/**
*
* Implementación específica de clasificación rápida, clasificación en orden inverso
*
* @param datos
* @param bajo
* @param alto
*
*/
privado vacío qsort_desc (int datos [], int bajo, int alto) {
int i, j, x;
if (low < high) { // Esta condición se utiliza para finalizar la recursividad
yo = bajo;
j = alto;
x = datos[i];
mientras (yo < j) {
mientras (i < j && datos[j] < x) {
j--; // Encuentra el primer número menor que x de derecha a izquierda
}
si (yo <j) {
datos[i] = datos[j];
yo ++;
}
mientras (i < j && datos[i] > x) {
i++; // Encuentra el primer número mayor que x de izquierda a derecha
}
si (yo <j) {
datos[j] = datos[i];
j--;
}
}
datos[i] = x;
qsort_desc(datos, bajo, i - 1);
qsort_desc(datos, i + 1, alto);
}
}
/**
*
* Búsqueda binaria de la posición de un número entero específico en una matriz de enteros (recursiva)
*
* La lista lineal de búsqueda debe ser una lista ordenada
*
* @paramdataset
* @paramdata
* @parambeginIndex
* @paramendIndex
* @returnindex
*
*/
público int binarioSearch(int[] conjunto de datos, int datos, int startIndex,int endIndex) {
int midIndex = (beginIndex + endIndex) >>> 1; // Equivalente a mid = (bajo + alto)
// / 2, pero la eficiencia será mayor
if (datos < conjunto de datos[beginIndex] || datos > conjunto de datos[endIndex] || comenzarIndex > endIndex)
devolver -1;
if (datos <conjunto de datos[midIndex]) {
devolver binarioSearch(conjunto de datos, datos, comenzarIndex, midIndex - 1);
} else if (datos > conjunto de datos[midIndex]) {
devolver binarioSearch(conjunto de datos, datos, midIndex + 1, endIndex);
} demás {
devolver índice medio;
}
}
/**
*
* Búsqueda binaria de la posición de un número entero específico en una matriz de enteros (no recursiva)
*
* La lista lineal de búsqueda debe ser una lista ordenada
*
* @paramdataset
* @paramdata
* @returnindex
*
*/
público int binarioSearch(int[] conjunto de datos, int datos) {
int índicecomienzo = 0;
int endIndex = conjunto de datos.longitud - 1;
int índice medio = -1;
if (datos < conjunto de datos[beginIndex] || datos > conjunto de datos[endIndex] || comenzarIndex > endIndex)
devolver -1;
mientras (inicioIndex <= endIndex) {
midIndex = (beginIndex + endIndex) >>> 1; // Equivalente a midIndex =
// (comienzo del índice +
// endIndex) / 2, pero la eficiencia será mayor
if (datos <conjunto de datos[midIndex]) {
índice final = índice medio - 1;
} else if (datos > conjunto de datos[midIndex]) {
comenzarIndice = midIndex + 1;
} demás {
devolver índice medio;
}
}
devolver -1;
}
público estático vacío principal (String [] argumentos) {
Ordenar sortTest = new Sort();
int[] matriz = sortTest.createArray();
System.out.println("==========Después de la clasificación de burbujas (orden positivo)==========");
sortTest.bubbleSort(matriz, "asc");
System.out.println("==========Después de ordenar las burbujas (orden inverso)==========");
sortTest.bubbleSort(array, "desc");
matriz = sortTest.createArray();
System.out.println("==========Después de invertir la matriz==========");
sortTest.reverse(matriz);
matriz = sortTest.createArray();
System.out.println("==========Después de la clasificación por selección (orden positivo)==========");
sortTest.selectSort(matriz, "asc");
System.out.println("==========Después de la clasificación por selección (orden inverso)==========");
sortTest.selectSort(array, "desc");
matriz = sortTest.createArray();
System.out.println("==========Después de la inserción ordenar (secuencia positiva)==========");
sortTest.insertSort(matriz, "asc");
System.out.println("==========Después de la inserción ordenar (orden inverso)==========");
sortTest.insertSort(array, "desc");
matriz = sortTest.createArray();
System.out.println("==========Después de la clasificación rápida (orden positivo)==========");
sortTest.quickSort(matriz, "asc");
sortTest.printArray(matriz);
System.out.println("==========Después de la clasificación rápida (orden inverso)==========");
sortTest.quickSort(array, "desc");
sortTest.printArray(matriz);
System.out.println("==========Búsqueda binaria en matriz==========");
System.out.println("El número que busca está en" + sortTest.binarySearch(array, 74)
+ "asientos. (Subíndice calculado a partir de 0)");
}
}