A classificação rápida me fez olhar para isso por muito tempo e me torturou por muito tempo, porque tenho a ideia geral, mas sempre surgem vários problemas ao escrever código. Ainda é difícil para mim depurá-lo pessoalmente. um certo grau de dificuldade, e por trabalho e preguiça, os erros que não podiam ser depurados já foram guardados há muito tempo. Hoje finalmente saiu, e ainda estou um pouco animado. Deixe-me compartilhar meu código e dar. uma pequena explicação.
Para aprender a classificação rápida, você deve primeiro aprender o método de dividir e conquistar. A ideia de dividir e conquistar é fornecer uma sequência de números fora de ordem (os números são suposições, eles também podem ser outros objetos. Claro, os parâmetros do método podem ser definidos por você mesmo (estou aqui, suponha que haja uma matriz de números inteiros) e depois forneça a ele. Um número do meio, o método de dividir e conquistar dividirá esses números em duas partes com base no número do meio fornecido a ele, uma parte está à esquerda do número do meio e a outra parte está à direita. ponto de divisão, os números de ambos os lados ainda estão fora de ordem, a forma como defini é a seguinte:
//esquerda é a extremidade esquerda da parte de divisão e conquista do array, e direita é a extremidade total da parte de divisão e conquista da matriz. Por exemplo, para uma matriz com comprimento de 10, if. Quero dividir e conquistar os 5 primeiros inteiros, posso passar 0 ou 4 como public int signalFenZhi(int left,int right){ if(left<0||left>n-1||right<0||right> n-1){ return -1 } int temp = teste[esquerda]; j=direita; int i=esquerda; while(i<j){ while(teste[j]>=teste[esquerda]&&i<j){ j--; &&i<j){ i++ } if(i<j){ temp = teste[i]=teste[j]=temp; = teste[eu]; teste[i]=teste[esquerda]; teste[esquerda]=temp } for(int m=0;m<n;m++){ System.out.print(teste[m]+" "); ;Claro, você também pode passar o número do meio como parâmetro. Agora, apenas uso o número da esquerda passado como número de divisão.
Depois de entender dividir e conquistar, a classificação rápida é simples. Ou seja, dividir e conquistar os números que foram divididos em duas partes, e assim por diante, até que todos os números estejam em ordem.
public void quickSort(int esquerda,int direita){ if(direita-esquerda<1){ return }else{ int ponto = this.signalFenZhi(esquerda, direita); ponto!=esquerda&&ponto!=direita){ quickSort(esquerda,ponto-1); quickSort(ponto+1,direita);A eficiência da classificação rápida é excelente entre muitos algoritmos de classificação. A complexidade do tempo é O(N*log2n). No entanto, se o ponto de divisão de divisão e conquista não for bem escolhido, a complexidade do tempo será reduzida para (n ao quadrado). ), porque se esse array for classificado e então pegarmos o número mais à esquerda passado todas as vezes, a eficiência será muito baixa, então devemos evitar essa situação. Se todas as opções forem testadas, será preciso muito. tempo, então Um método de compromisso é adicionar um número do meio ao número mais à esquerda e ao número mais à direita e encontrar o número do meio entre eles. Usar isso como valor de divisão tornará as coisas melhores. Com base no método acima, o código modificado é o seguinte. mas depois que terminei, essa abordagem não ficou muito boa. Seria melhor passar o valor da divisão como um método de dividir e conquistar, mas não vou tentar aqui.
pacote com.jll; public class FenZhi { int[] teste; int n=10; public FenZhi(){ teste = new int[10]; =(int)(Math.random()*100)+1; System.out.print(teste[i]+" "); n){ if(n>0){ this.n=n; teste = new int[n]; for(int i=0;i<n;i++){ teste[i]=(int)(Math.random ()*100)+1; public int signalFenZhiMajorizationFirst(int esquerda,int direita){ if(esquerda<0||esquerda>n-1||direita<0||direita>n-1||esquerda>=direita){ return -1; (direita+esquerda)/2; if(teste[esquerda]>teste[meio]){ int temp = teste[meio] = teste[esquerda] = temp }; if(teste[esquerda]>teste[direita]){ int temp = teste[esquerda]; teste[esquerda] = teste[direita] = temp } if(teste[meio]>teste[direita]; ){ int temp = teste[meio]; teste[meio] = teste[esquerda]; = temp; ]<=teste[esquerda]&&i<j){ i++ } if(i<j){ temp = teste[i];teste[j]; eu==j){ temp = teste[i]; teste[i]=teste[esquerda]; teste[esquerda]=temp } /*if(i==j){ temp = teste[meio]; ]; teste[i]=temp;*/ /*for(int m=0;m<n;m++){ System.out.print(teste[m]+" "); outro { if(teste[direita]<teste[esquerda]){ int temp = teste[direita]; teste[esquerda]; ,int direita){ if(direita-esquerda<1){ return }else{ int ponto = this.signalFenZhiMajorizationFirst(esquerda, direita); é: "+ponto); quickSortMajorizationFirst(esquerda,ponto-1); quickSortMajorizationFirst(ponto+1,direita); } } 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); }}O código é executado da seguinte maneira:
95 40 64 18 78 23 73 84 40 o ponto é:4o ponto é:1o ponto é:3o ponto é:7o ponto é:6o ponto é:918 23 40 40 64 73 78 84 95
O que foi dito acima é o que aprendi, registre-o para referência futura.