Conceito de algoritmo de classificação rápida
A classificação rápida geralmente é baseada na implementação recursiva. A idéia é a seguinte:
1. Selecione um valor apropriado (o valor ideal é o melhor, mas o primeiro valor na matriz é geralmente usado na implementação), que é chamado de "pivô".
2. Com base nesse valor, divida a matriz em duas partes, a parte menor à esquerda e a parte maior à direita.
3. É certo que, após uma rodada, a posição deste pivô deve estar na posição final.
4. Repita o processo acima para os dois subarrays até que haja apenas um elemento por matriz.
5. A classificação é concluída.
Método de implementação básica:
public static void Quicksort (int [] arr) {qsort (arr, 0, arr.length-1);} private estático vazio Qsort (int [] arr, int baixo, int alto) {if (baixo <alto) {int pivot = partition (arr, baixo, alto); // Divida a matriz em duas partes Qsort (arr, baixa, pivot-1); // Classifique o subarray esquerdo qsort (arr, pivô+1, alto); // Classifique a subarray certa recursivamente}} Partição estática privada int (int [] arr, int baixo, int alto) {int pivot = arr [baixo]; // registro de pivô while (baixo <alto) {while (baixo <High && arr [High]> = Pivot) - -High; arr [baixo] = arr [alto]; // Os registros de troca menores que o pivô para a esquerda (BOW <High && arr [Low] <= pivot) ++ baixo; arr [alto] = arr [baixo]; // Os registros de troca menores que o pivô para a extremidade direita} // varrem é concluído e o pivô está no lugar arr [baixo] = pivot; // retorna a posição do pivô ao retorno baixo;}Use genéricos para implementar o algoritmo de ordem rápida
Abaixo está uma classe do QuickSort, que contém o tipo de função estática (), que pode classificar matrizes de qualquer tipo. Se for uma matriz de tipos de objetos, o tipo de objeto deve implementar a interface comparável, para que a função Comparisonto possa ser usada para comparação.
O algoritmo de classificação de linha rápida mais básica foi usada e nenhum processamento de otimização foi realizado.
O código -fonte é o seguinte:
importar java.util.LinkedList; importar java.util.list; importar java.util.ListIterator; importar java.util.random; classe pública QuickSort {@suppresswarnings ("desmarcado") // Modifique o protótipo da função de ruptura rápida acima para que possa classificar matrizes de qualquer tipo de objeto. Esta função é usada internamente e a interface da função de classificação externa é classificada (). A função de classificação requer que o objeto implemente a interface comparável, que pode fornecer detecção de tipo de tempo de compilação, consulte o artigo a seguir. private estático void Quicksort (objeto [] in, int Begin, int end) {if (begin == end || BEGIN == (end-1)) retornar; Objeto p = em [BEGIN]; int a = comece +1; int b = a; para (; b <end; b ++) {// Esta matriz de tipo de objeto deve implementar a interface comparável para que você possa usar a função compareto para comparação se (((comparável <ject>) em [b]). compareto (p) <0) {if (a == b) {a ++; continue;} objeto temp = em [a]; em [a] = em [b]; em [b] = temp; a ++; }} em [Begin] = em [a-1]; em [a-1] = p; if (a-1> BEGIN) {QuickSort (in, Begin, A); } if (end-1> a) {Quicksort (in, a, end); } retornar; } // Use genéricos para classificar qualquer matriz de objetos, a matriz do tipo de objeto deve implementar a interface comparável public static <t estende comparável <??? Super T >> Void Sort (t [] entrada) {QuickSort (entrada, 0, input.length); } // Adicione a função dos objetos da lista de classificação, consulte a função Sort () da classe java.util.Collections na estática pública java <t estende comparável <?? super t >> void Sort (list <T> list) {object [] t = list.toarray (); // Converta a lista em uma matriz Quicksort (t, 0, t.Length); // Classifique a matriz // Após a classificação da matriz ser concluída, escreva de volta ao listiterator <t> i = list.ListIterator (); for (int j = 0; j <t.Length; j ++) {i.next (); i.set ((t) t [j]); }} // Como os genéricos não podem ser usados em Java, tipos de dados primitivos (int, duplo, byte, etc.), você pode usar apenas o mecanismo de sobrecarga de função para classificar essas matrizes primitivas (int [], duplo [], byte [], etc.). Para compartilhar a mesma função de classificação, o mecanismo de tipo original (auto -boxing, unboxing) é usado para encapsulá -lo no tipo de objeto correspondente, formar uma nova matriz de objetos, classificá -lo e depois dei -se devagar. A desvantagem disso é que ele requer etapas adicionais de conversão e espaço adicional para salvar a matriz encapsulada. Outra maneira é copiar o código de classificação para cada função sobrecarregada. A função stor () na classe java.util.Arrays na API oficial usa esse método, que pode ser visto no código -fonte da classe Matriz. public static void Sort (int [] input) {Integer [] t = new Integer [input.length]; para (int i = 0; i <input.length; i ++) {t [i] = entrada [i]; // encapsulamento} Quicksort (t, 0, t.Length); // classificação para (int i = 0; i <input.length; i ++) {input [i] = t [i]; classificar (duplo [] input) {duplo [] t = novo duplo [input.length]; for (int i = 0; i <input.length; i ++) {t [i] = entrada [i]; } QuickSort (t, 0, t.Length); for (int i = 0; i <input.length; i ++) {input [i] = t [i]; }} // Função de sobrecarga do byte [] Array public static void Sort (byte [] input) {byte [] t = novo byte [input.length]; for (int i = 0; i <input.length; i ++) {t [i] = entrada [i]; } QuickSort (t, 0, t.Length); for (int i = 0; i <input.length; i ++) {t [i] = entrada [i]; } QuickSort (t, 0, t.Length); for (int i = 0; i <input.length); input.Length; i ++) {input [i] = t [i]; }} // Função de sobrecarga curta for (int i = 0; i <input.length; i ++) {t [i] = entrada [i]; } QuickSort (t, 0, t.Length); for (int i = 0; i <input.length; i ++) {input [i] = t [i]; }} // Função de sobrecarga curta for (int i = 0; i <input.length; i ++) {t [i] = entrada [i]; } QuickSort (t, 0, t.Length); for (int i = 0; i <input.length; i ++) {input [i] = t [i]; }} // Função de sobrecarga da matriz [] Public Static Void Sort (float [] input) {float [] t = new float [input.length]; for (int i = 0; i <input.length; i ++) {t [i] = entrada [i]; } QuickSort (t, 0, t.Length); for (int i = 0; i <input.length; i ++) {input [i] = t [i]; }} // A principal função para testar o vazio estático público principal (string [] args) {// produz uma matriz int [] composta por números aleatórios para testar int len = 10; int [] input = new int [len]; Aleatório r = novo aleatório (); System.out.print ("int [] antes de classificar:"); for (int i = 0; i <input.length; i ++) {input [i] = r.nextint (10*len); System.out.print (entrada [i] + ""); } System.out.println (); System.out.print ("int [] após classificar:"); classificar (entrada); for (int i: input) {System.out.print (i + ""); } System.out.println (); // gera uma matriz de strings para testar a string [] s = new String [] {"b", "A", "E", "D", "F", "C"}; System.out.print ("String [] antes de classificar:"); for (int i = 0; i <S.LenLength; i ++) {System.out.print (s [i]+""); } System.out.println (); System.out.print ("String [] Após a classificação:"); tipo (s); for (int i = 0; i <S.LenLength; i ++) {System.out.print (s [i]+""); } System.out.println (); // Gere uma lista de strings para a lista de testes <String> l = new LinkedList <String> (); s = new String [] {"B", "A", "E", "D", "F", "C"}; System.out.print ("LinkedList <String> antes de classificar:"); for (int j = 0; j <comprimento; j ++) {l.add (s [j]); System.out.print (s [j] + ""); } System.out.println (); classificar (l); System.out.print ("LinkedList <String> Após a classificação:"); for (string ts: l) {System.out.print (ts + ""); } System.out.println (); }}Execute o teste de função principal e, a partir da saída, você pode ver que a classe do Quicksort está funcionando normalmente:
int [] Antes de classificar: 65 48 92 26 3 8 59 21 16 45int [] Após a classificação: 3 8 16 21 26 45 48 59 65 92String [] Antes de classificar: Baedfc String [] Após a classificação: ABCDEF LinkedList <String> Antes de classificar: BAEDFC Linkedlist <String> STAWEL