La clasificación rápida me ha obligado a mirarlo durante mucho tiempo y me ha torturado durante mucho tiempo, porque tengo una idea general, pero siempre surgen varios problemas al escribir código. Personalmente, todavía me resulta difícil depurarlo. Un cierto grado de dificultad, y debido al trabajo y la pereza, los errores que no se pudieron depurar se han guardado durante mucho tiempo. Hoy finalmente está disponible y todavía estoy un poco emocionado. una pequeña explicación.
Para aprender a ordenar rápidamente, primero debe aprender el método de dividir y conquistar. La idea de divide y vencerás es dar una cadena de números desordenados (los números son suposiciones, también pueden ser otros objetos). Por supuesto, los parámetros del método los puede definir usted mismo. (Supongamos que hay una matriz de números enteros) y luego dárselos. Un número medio, el método divide y vencerás dividirá estos números en dos partes según el número medio que se le haya asignado, una parte está a la izquierda del número medio y la otra parte está a la derecha usando este número como. punto de división, los números en ambos lados todavía están desordenados, la forma en que lo definí es la siguiente:
//izquierda es el punto final izquierdo de la parte de divide y vencerás de la matriz, y derecha es el punto final total de la parte de divide y vencerás de la matriz. Por ejemplo, para una matriz con una longitud de 10, si. Quiero dividir y conquistar los primeros 5 números enteros, puedo pasar 0 o 4 como public int signalFenZhi(int left,int right){ if(left<0||left>n-1||right<0||right> n-1){ retorno -1; } int temp = prueba[izquierda]; j=derecha; int i=izquierda; mientras(i<j){ mientras(prueba[j]>=prueba[izquierda]&&i<j){ j--; &&i<j){ i++ } if(i<j){ temp = prueba[i]; prueba[i]=prueba[j]=temp } } if(i==j){ temp; = prueba[yo]; prueba[i]=prueba[izquierda]; prueba[izquierda]=temp } for(int m=0;m<n;m++){ System.out.print(prueba[m]+" "); ; }
Por supuesto, también puedes pasar el número del medio como parámetro. Ahora solo uso el número de la izquierda pasado como número divisor. Esto es solo para ilustración.
Después de comprender divide y vencerás, la clasificación rápida es simple, es decir, dividir y conquistar los números que se han dividido en dos partes, y así sucesivamente, hasta que todos los números estén en orden.
public void quickSort(int izquierda,int derecha){ if(derecha-izquierda<1){ return }else{ int punto = this.signalFenZhi(izquierda, derecha); punto!=izquierda&&punto!=derecha){ clasificación rápida(izquierda,punto-1); clasificación rápida(punto+1,derecha);
La eficiencia de la clasificación rápida es excelente entre muchos algoritmos de clasificación. La complejidad del tiempo es O (N*log2n). Sin embargo, si el punto de división de divide y vencerás no se elige bien, la complejidad del tiempo se reducirá a (n al cuadrado). ), porque si esta matriz está ordenada y luego tomamos el número más a la izquierda cada vez, la eficiencia será muy baja, por lo que debemos evitar esta situación. Si se prueban todas las opciones, se necesitarán muchas. tiempo, entonces Un método de compromiso es agregar un número del medio al número más a la izquierda y al número más a la derecha, y encontrar el número del medio entre ellos. Usar esto como valor de división mejorará las cosas. Según el método anterior, el código modificado es el siguiente. Pero después de terminarlo, este método no es muy bueno. Sería mejor pasar el valor de división como un método de dividir y conquistar, pero yo no lo intentaré aquí.
paquete com.jll; clase pública FenZhi { int[] prueba; int n=10; pública FenZhi(){ prueba = nueva int[10]; =(int)(Math.random()*100)+1; System.out.print(prueba[i]+" "); System.out.println() } público FenZhi(int); n){ if(n>0){ this.n=n; prueba = nuevo int[n]; para(int i=0;i<n;i++){ prueba[i]=(int)(Math.random ()*100)+1; } } } señal int públicaFenZhiMajorizationFirst(int izquierda,int derecha){ if(izquierda<0||izquierda>n-1||derecha<0||derecha>n-1||izquierda>=derecha){ return -1 } if(derecha-izquierda>=2){ int middle = (derecha+izquierda)/2; if(prueba[izquierda]>prueba[medio]){ int temp = prueba[medio]; prueba[izquierda]; if(prueba[izquierda]>prueba[derecha]){ int temp = prueba[izquierda]; prueba[izquierda] = prueba[derecha] = temp } if(prueba[medio]>prueba[derecha] ){ int temp = prueba[medio]; prueba[medio] = prueba[derecha] = prueba } int temp = prueba[medio]; = temp; int j=derecha-1; int i=izquierda+1; mientras(i<j){ mientras(prueba[j]>=prueba[izquierda]&&i<j){ j--; ]<=prueba[izquierda]&&i<j){ i++ } if(i<j){ temp = prueba[i]; prueba[j]=temp; yo==j){ temperatura = prueba[i]; prueba[i]=prueba[izquierda]; prueba[izquierda]=temp } /*if(i==j){ temperatura = prueba[medio]; ]; prueba[i]=temp; }*/ /*for(int m=0;m<n;m++){ System.out.print(prueba[m]+" "); demás { if(prueba[derecha]<prueba[izquierda]){ int temp = prueba[derecha]; prueba[derecha] = prueba[izquierda] = temp } return derecha; ,int derecha){ if(derecha-izquierda<1){ retorno }else{ int punto = this.signalFenZhiMajorizationFirst(izquierda, derecha); es: "+punto); QuickSortMajorizationFirst (izquierda, punto-1); QuickSortMajorizationFirst (punto + 1, derecha); } } public static void main(String[] args) { FenZhi f = new FenZhi(); System.out. println(f.signalFenZhiMajorizationFirst(0, 9)); System.out.println(); f.quickSortMajorizationFirst(0,fn-1); //f.quickSort(0,f.test.length-1); for(int i:f.test){ System.out.print(i+" "); }}
El código se ejecuta de la siguiente manera:
95 40 64 18 78 23 73 84 40 el punto es:4 el punto es:1 el punto es:3 el punto es:7 el punto es:6 el punto es:918 23 40 40 64 73 78 84 95
Lo anterior es lo que aprendí, regístrelo para referencia futura.