Cada programador debe pensar inicialmente en el esquema/plan/arquitectura del trabajo futuro; de lo contrario, todo terminará en un desastre, en completa anarquía. Como ocurre con cualquier publicación, inicialmente necesitas un plan, comencemos.
1) Tomemos el tema de la ordenación por combinación para principiantes.
2) Crearemos una arquitectura y un plan para el trabajo futuro.
3) Trabajaremos y describiremos todas las partes del plan.
4) Comprobemos el rendimiento y la calidad.
2.1) ¿Qué es la clasificación por combinación?
2.2) Descripción de posibles firmas.
2.3) Da un ejemplo.
2.4) Describe la implementación en Java usando un ejemplo.
2.5) Cualquier cosa extra.
Fusionar: ordenar por fusión en Java
Implica el principio de “divide y vencerás”. ¿Cuál es la idea y su significado?
Clasificación.
Dividimos el array en partes hasta que sea igual a 1 elemento. Cada 1 elemento está ordenado.
Fusión.
Fusionando elementos ordenados.
Basado en el principio de dos barajas de cartas. Colocamos 2 mazos de cartas sobre la mesa con sus valores hacia arriba, y la carta que tenga más bajo se coloca en la tercera pila de cartas resultante. En última instancia, si nos quedamos sin cartas en un determinado mazo, las movemos una a una al mazo resultante. El resultado será una combinación de dos matrices ordenadas, una nueva matriz ordenada.
Esto es más o menos lo mismo, sólo que vinculado a índices. Las variables en ellos son:
A=Array= Массив
p, q, r = индексы для массива
p - начало первого массива
q - конец первого массива
q +1- начало второго массива
r - конец второго массива
Si estas variables no se describen, entonces el que pide realizar dicha función por sí mismo no sabe lo que quiere. Y tendrás que buscar en Google para descubrir qué es, probablemente lo encuentres, tal vez. Pongamos un ejemplo de nuestra clasificación. Hay una matriz {6, 1, 3, 5, 2, 4, 7, 8}, si su longitud es mayor que 1, entonces la dividimos en 2 partes y obtenemos la parte izquierda {6, 1, 3, 5}y la parte derecha {2, 4, 7, 8}. Continuamos la acción de dividir en 2 partes hasta que su longitud sea mayor que 1. Como resultado, obtenemos un montón de matrices con una longitud de 1 elemento, a saber: {6} {1} {3} {5} {2} {4} {7} {8}. La implementación en Java es algo como esto:
publicint[]sortArray(int[] arrayA){// clasificación Массива который передается в функцию// проверяем не нулевой ли он?if(arrayA ==null){returnnull;}// проверяем не 1 ли элемент в массиве?if(arrayA.length <2){return arrayA;// возврат в рекурсию в строки ниже см комменты.}// копируем левую часть от начала до серединыint[] arrayB =newint[arrayA.length /2];System.arraycopy(arrayA,0, arrayB,0, arrayA.length /2);// копируем правую часть от середины до конца массива, вычитаем из длины первую частьint[] arrayC =newint[arrayA.length - arrayA.length /2];System.arraycopy(arrayA, arrayA.length /2, arrayC,0, arrayA.length - arrayA.length /2);// рекурсией закидываем поделенные обе части обратно в наш метод, он будет крутится до тех пор,// пока не дойдет до 1 elemento в массиве, после чего вернется в строку и будет искать второй такой же,// точнее правую часть от него и опять вернет его назад
arrayB =sortArray(arrayB);// левая часть возврат из рекурсии строкой return arrayA;
arrayC =sortArray(arrayC);// правая часть возврат из рекурсии строкой return arrayA;// далее опять рекурсия возврата слияния двух отсортированных массивовreturnmergeArray(arrayB, arrayC);}
A continuación, debe fusionar estas matrices en 1. ¿Cómo se hace esto? Para evitar revisar cada matriz varias veces, ingresemos índices de posición para cada matriz. Luego recorreremos un bucle una vez, igual a la longitud de la suma de estas dos matrices. Tome la primera matriz y la segunda matriz, y tome el primer elemento, compare el elemento número 1 en la primera matriz y el elemento número 1 en la segunda matriz . El más pequeño se coloca en la matriz resultante. Es importante aquí que si tomamos un elemento de la primera matriz, cuando pase el bucle, debe hacer referencia al segundo elemento de la primera matriz y al primer elemento de la segunda matriz. Para hacer esto, debe aumentar el índice de la segunda matriz en +1 y, al verificar, restarlo del número de ciclo, de manera similar para la primera matriz. ¿Está claro por qué hacer esto? ¿O no hay nada claro? :-) Por ejemplo, hay 2 matrices: {1}{4}{8}y {3}{6}{7} Y hay un bucle:
for(int i =0; i < arrayA.length + arrayB.length; i++){if(arrayA[i]< arrayB[i]){
arrayC[i]= arrayA[i];}else{
arrayC[i]= arrayB[i];}}
En la primera pasada del ciclo, resultará que arrayC[1] = {1}: tomamos este elemento de la primera matriz. Luego, al pasar por el segundo bucle, ya debemos comparar el elemento {4}y {3}, pero para ello debemos tener en cuenta los índices de posición y el desplazamiento de ambos arrays, para ello los ingresamos.
int positionA =0, positionB =0;for(int i =0; i < arrayA.length + arrayB.length; i++){if(arrayA[i - positionA]< arrayB[i - positionB]){
arrayC[i]= arrayA[i - positionA];
positionB++;}else{
arrayC[i]= arrayB[i - positionB];
positionA++;}}
Pero eso no es todo, hay que tener en cuenta que alguna matriz puede terminar antes. Por ejemplo, hay 3 matrices: {1}{3}{5}y {6}{7}{9} la primera matriz terminará antes de que llegue la segunda, para ello es necesario ingresar un cheque y, en principio, la función de fusión está lista.
Lo más difícil de esta clasificación es el principio de transición recursiva. Aquellos. Lanzamos el lado izquierdo a la recursividad hasta que sea divisible por 2, y luego lo desenrollamos hacia atrás, en palabras es muy complicado y confuso, pero cuando intentas imaginar, si aún no está claro, entonces es un completo desastre. Tomemos la matriz: {2}{1}{4}{3}. La primera recursividad de clasificación lo dividirá en 2 partes y ejecutará la función nuevamente con los elementos 2-1 , luego nuevamente con los elementos 2 y 1 , los devolverá uno por uno, de modo que entrarán primero en la función de combinación y vendrán 1-2. afuera , entonces la recursión regresará y arrojará 4-3 a la combinación , luego 4 y 3 , después de lo cual la combinación devolverá 3-4 , y solo entonces la recursividad volverá a girar nuevamente y 1-2 y 3-4 se incluirá en la combinación y la matriz ordenada se devolverá 1-2-3-4 . Bueno, eso es todo, la clasificación consta de dos funciones.
sortArray(array);// кладем массив который нужно отсортироватьmergeArray(arrayA, arrayB);// кладем 2 массива которые нужно слить в один
Si escribe algún tipo de main, obtendrá algo como:
publicstaticvoidmain(String[] args){Merge testMerge =newMerge();int[] result = testMerge.sortArray(newint[]{2,3,1,4});for(int i =0; i < result.length ; i++){System.out.print(result[i]+" ");}}
Para mí, esta clasificación fue un completo fracaso, había un millón de preguntas, pero no había respuestas, busqué en Internet, releí, vi un montón de videos, pero como siempre, solo encontré las respuestas yo mismo. Y solo cuando comencé a escribir una solución completamente diferente a la que parpadea en todas partes) Pero al final resultó similar a todas las demás))) Ordenar es en realidad lo más simple, lo principal es presentarlo de forma interactiva en acción, y todo encaja en su lugar si lo dominas, haré un video)))) Hasta ahora, eso es todo para lo que he tenido suficiente: Combinar ordenar Combinar ordenar Lo más importante es siempre hacer un plan desde el principio. Es mejor esperar un poco y pensar antes de empezar a hacer cualquier cosa. Puede que lleve más tiempo, pero surgirá una comprensión y una solución en lugar de tener que reescribirlo un par de veces y buscar muletas. Gracias a todos por su tiempo, buena suerte y buen humor. ) PD: Las críticas, buenas y malas, así como las preguntas son bienvenidas. )))
GO TO FULL VERSION