Visão geral
A classificação rápida é um algoritmo de classificação desenvolvido por Tony Hall. Na situação média, a ordem dos n itens exige uma comparação (nLogn). De fato, a classificação rápida geralmente é significativamente mais rápida do que outros algoritmos (nLogn), porque seu loop interno pode ser implementado com eficiência na maioria das arquiteturas e, na maioria dos dados do mundo real, pode determinar a escolha do design e reduzir a possibilidade de termos quadráticos que requerem tempo.
Classificação rápida, divida os registros a serem classificados em duas partes independentes por meio de uma ordem, onde as palavras -chave de alguns registros são menores que as palavras -chave da outra parte e, em seguida, os dois registros continuam sendo classificados separadamente para alcançar o objetivo de ordenar toda a sequência.
Ilustração da imagem:
etapa
Ao selecionar um elemento de referência, o primeiro elemento ou o último elemento geralmente é selecionado para dividir os registros a serem classificados em duas partes independentes por meio de uma série, onde os valores do elemento de alguns registros são menores que os valores do elemento de referência. Os elementos registrados na outra parte são maiores que o valor de referência. Nesse momento, os elementos de referência estão na posição correta após serem classificados e, em seguida, as duas partes dos registros continuam sendo classificadas da mesma maneira até que toda a sequência seja ordenada.
Exemplo
Dados brutos:
3 5 2 6 2
Selecione 3 como o benchmark
A primeira rodada
Da direita para a esquerda para encontrar algo menor que 3, 2 correspondências e ajustar 2 e 3 2 5 2 6 3 uma vez, e a direção da pesquisa é revertida, da esquerda para a direita para encontrar algo maior que 3, 5 correspondências e ajustar 2 3 2 6 5 e depois da direita para a esquerda para encontrar algo menor que 3, 2 correspondências e ajuste 2 2 3 6 5 ONE RODA
Rodada 2
O mesmo método acima é realizado para [2 2] e 2 2 3 6 5
A terceira rodada
O mesmo método acima é realizado para [6 5] e 2 2 3 5 6
Resultado final
2 2 3 5 6
Implementação de código (Java)
pacote com.coder4j.main.arithmetic.sorting; classe pública Quick {private static int mark = 0; / ** * Método de troca auxiliar * * @param Array * @param a * @param b */ private estático void swap (int [] matriz, int a, int b) {if (a! = B) {int temp = matriz [a]; array [a] = array [b]; matriz [b] = temp; // Encontre a correspondência, switch System.out.println ("shift" + array [a] + "e" + matriz [b] + ", get"); para (int i: Array) {System.out.print (i + ""); } System.out.println (); }} / ** * Nova rodada de separação * * @param Array * @param low * @param alto * @return * / private static int partition (int array [], int baixo, int alto) {int base = array [baixo]; Mark ++; System.out.println ("tiro em andamento" + mark + "separação de rodas, área:" + baixa + "-" + alta); while (baixo <alto) {while (baixo <High && Array [High]> = Base) {High--; System.out.println ("da direita para a esquerda para encontrar a proporção" + base + "pequena, alteração do ponteiro:" + baixa + "-" + alta); } troca (matriz, baixa, alta); while (baixo <High && Array [Low] <= base) {Low ++; System.out.println ("da esquerda para a direita para encontrar a proporção" + base + "grande, alteração do ponteiro:" + baixa + "-" + alta); } troca (matriz, baixa, alta); } retornar baixo; } / ** * Classificação rápida da matriz, ligue recursivamente * * @param Array * @param Low * @param altura * @return * / private static int [] Quicksort (int [] array, int baixo, int alting) {if (Low <alting <altion) {int division = partition (array, baixa, altura); Quicksort (Array, Low, Divisão - 1); Quicksort (Array, Divisão + 1, Altura); } retornar a matriz; } / ** * Classificação rápida * * @param Array * @return * / public static int [] classy (int [] array) {return quicksort (array, 0, array.length - 1); } public static void main (string [] args) {int [] array = {3, 5, 2, 6, 2}; int [] classificado = classificar (matriz); System.out.println ("resultado final"); para (int i: classificado) {System.out.print (i + ""); }}}Resultados da saída de teste:
Selecione tudo e coloque -o nas notas. A primeira rodada de separação está sendo realizada. Área: 0-4. A segunda rodada de ajustes é 2 e 3. A segunda rodada de separação é 2 5 2 6 3. A segunda rodada de separação é 3 e 5. A segunda rodada de separação é 2 3 2 6 5. A segunda rodada de separação é 3 e 6. A segunda rodada de separação é 2 e 3. A segunda rodada é 2 e 3. A segunda rodada é 2 e 3. A separação é 2 e 3. A segunda rodada de separação é 2 e 3. A segunda rodada de separação é 2 e 3. A segunda rodada de separação é 2 e 2 é 3. O último resultado é 2 2 3 5 6.
Após o teste, é consistente com os resultados no exemplo.