Comparado com algoritmos como classificação de bolhas, classificação de seleção etc., os princípios específicos do algoritmo e a implementação da classificação rápida são difíceis. Para entender melhor a classificação rápida, ainda descrevemos os princípios algorítmicos de classificação rápida em detalhes na forma de exemplos. No algoritmo de classificação anterior, usaremos o problema de classificação de altura de 5 atletas como exemplo para explicá -lo. Para refletir melhor as características da classificação rápida, adicionaremos mais 3 atletas aqui. Os 8 atletas e suas informações de altura no exemplo são as seguintes (F, G, H são novos atletas): A (181), B (169), C (187), D (172), E (163), F (191), G (189), H (182)
No algoritmo de classificação anterior, essas classificações foram todas feitas pelo treinador. Agora que o número de atletas aumentou, o treinador também quer aproveitar a oportunidade para fazer uma pausa, então o treinador ligou para dois assistentes e pediu aos dois assistentes que classificassem as alturas dos 8 atletas da esquerda para a direita e baixa e alta de uma maneira rápida de classificação.
De acordo com o princípio do algoritmo do método de classificação rápida, os dois assistentes ficam de ambos os lados do arranjo do atleta, como mostrado na figura abaixo:
Primeiro, o Assistente 1 seleciona um atleta do acordo (geralmente seleciona o primeiro atleta à esquerda ou do atleta do meio) e aqui seleciona o atleta A (181). Como a classificação é da esquerda para a direita e da baixa a alta, o assistente 1 exige que um atleta que seja menor em altura que um (181) (o A (181) selecionado é usado como referência para comparação. Todas as comparações nesta rodada são comparadas com o atleto inicialmente selecionado (181)):
Vamos continuar se referindo ao diagrama detalhado da primeira rodada de classificação rápida.
Quando os dois assistentes se reúnem durante o processo de classificação e pesquisa, a comparação da rodada atual é interrompida e o atleta A (181) inicialmente selecionado é colocado no espaço vazio onde os dois assistentes se encontram:
Em rápida classificação, esta rodada de classificação termina quando dois assistentes se encontram. Nesse momento, descobrimos que, usando a posição A (181), onde os dois atletas se encontraram como o ponto de divisão, os da esquerda são atletas menores que A (181), e os atletas à direita são maiores que A (181). Neste momento, separaremos os dois tipos no lado esquerdo e direito de um (181). Se continuarmos a classificar os arranjos de ambos os lados usando os métodos de classificação dos dois assistentes acima, após vários arranjos, finalmente obteremos os resultados de classificação de que precisamos.
O exposto acima é todo o processo de implementação de classificação de classificação rápida. A classificação rápida é usar as regras de classificação acima para dividir um arranjo em dois arranjos, e os dois arranjos em quatro arranjos até que não haja arranjo a ser dividido e, finalmente, obtemos o resultado de classificação de que precisamos.
Agora, ainda programamos o código Java para classificar as alturas dos 8 atletas acima usando a classificação rápida:
/** * Quick sorting of the elements in the specified array from start to end* * @param array The specified array* @param start The resulting point of the array inquiry that needs to be quickly sorted* @param end The end of the array index that needs to be quickly sorted*/public static final void quickSort(int[] array, int start, int end) { // i is equivalent to the position of assistant 1, j is equivalente à posição de assistente 2 int i = start, j = end; int pivot = array [i]; // Pegue o primeiro elemento como o elemento de referência int em vazio = i; // O índice de posição do espaço vazio é indicado, e o padrão é a posição do elemento de referência que está sendo recuperado // se houver mais de 1 elementos para classificar, insira classificação rápida (desde que i e j sejam diferentes, significa que pelo menos 2 elementos de matriz precisam ser classificados para a esquerda) enquanto (i <j) {// assistente 2 começa a procurar os elementos menores que o elemento de referência para a esquerda para a esquerda para a esquerda) enquanto (i <j) {//////cition JeaT), que é necessário, que se refere a uma referência para a esquerda) enquanto (i <j). if (i <j) {// Se o Assistente 2 encontrar o elemento correspondente antes de encontrar o Assistente 1, ele fornece o elemento às "vagas" do assistente 1, j se torna uma matriz espacial vazia [emoilindex] = matriz [emailindex = j]; } // Assistant 1 começa a procurar elementos maiores que o elemento de referência da esquerda para a direita (i <j && Array [i] <= pivot) i ++; Se (i <j) {// Se o Assistente 1 encontrar o elemento correspondente antes de encontrar o Assistente 2, ele fornecerá o elemento às "vagas" do assistente 2, e eu me tornar uma matriz vaga [emoilindex] = matriz [emailindex = i]; }} // Após o assistente 1 e o assistente 2, o loop será interrompido e o valor de referência inicial será levado para a última matriz vaga [emailindex] = pivot; // ===== Esta rodada de classificação rápida é concluída ===== // se houver mais de 2 elementos no lado esquerdo do ponto de divisão I, a chamada recursiva continuará a classificá -la rapidamente se (i - iniciar> 1) {Quicksort (Array, 0, i - 1); } // Se houver mais de 2 elementos no lado direito do ponto de divisão J, a chamada recursiva continua a classificá -la rapidamente se (end - j> 1) {QuickSort (Array, J + 1, final); }} // Método principal public estático void main (string [] args) {// ===== Classificar de baixo a alto usando o método de classificação rápida para representar as alturas de 8 atletas ===== // A (181), B (169), C (187), D (172), E (163), F (191), G (G (G. 187, 172, 163, 191, 189, 182}; // Ligue para o método de classificação rápido QuickSort (Heights, 0, Heights.Length - 1); // Resultado classificado por saída para (int altura: alturas) {System.out.println (altura); }}Os resultados da execução do código Java acima são emitidos da seguinte forma:
163169172181182187189191
NOTA: Devido às diferenças de pensamento local, pode haver várias variações na implementação de código classificado rápido acima. No entanto, não importa o que sejam as variantes, a idéia principal da classificação rápida não mudará.
Outra implementação: varredura unidirecional
Há outra versão de varredura unidirecional para fatia de matriz de classificação rápida. A etapa específica é selecionar o último elemento na matriz como elemento de fatiamento e definir dois ponteiros. O ponteiro I apoio para uma posição na frente do primeiro elemento da matriz, e J aponta para o primeiro elemento da matriz. J Digitalizações de frente para direita e direita. Ao encontrar um elemento de corte menor ou igual a, adicione i a um e depois troque os elementos apontados por i e j. Finalmente, troque os elementos na posição I+1 e os elementos de corte para concluir a divisão de matrizes. A implementação do código é a seguinte:
int partitio (int [] a, int lo, int hi) {int i = lo - 1, j = lo; int v = a [hi]; while (j <hi) {if (a [j] <= v) {swap (a, ++ i, j); } j ++; } troca (a, i + 1, oi); retornar i + 1;}