Como funciona a técnica de Quicksort em Java Trabalho?
Aqui, você descobrir como uma das técnicas de classificação mais comumente utilizados em Java realmente funciona. Esta técnica é denominada quicksort, e é um uso muito engenhosa de recursão.
Para a maioria de nós, para descobrir como algoritmos de ordenação, como o trabalho Quicksort é meramente um exercício intelectual. A API Java já triagem embutido.
A técnica Quicksort ordena um array de valores usando recursão. Seus passos básicos são assim:
Escolher um valor arbitrário, que se situa dentro da gama de valores na matriz.
Este valor é a ponto de pivô. A forma mais comum de escolher o ponto de pivô é simplesmente escolher o primeiro valor na matriz. Folks ter escrito doutorado sobre as formas mais sofisticadas para escolher um ponto de pivô que resulta em mais rápida triagem. Ficar com usando o primeiro elemento na matriz.
Reorganizar os valores na matriz de modo a que todos os valores que são menos do que o ponto de articulação está no lado esquerdo da matriz e todos os valores que são maiores do que ou igual ao ponto de articulação está no lado direito da matriz.
o valor pivot indica o limite entre o lado esquerdo e o lado direito da matriz. Ele provavelmente não vai ser morto, mas isso não importa. Este passo é chamado particionamento, e os lados esquerdo e direito das matrizes são partições.
Agora tratar cada uma das duas secções da matriz como uma matriz separada, e começar de novo com o Passo 1 para essa seção.
Essa é a parte recursiva do algoritmo.
A parte mais difícil do algoritmo Quicksort é o passo de particionamento, que deve reorganizar a partição de modo a que todos os valores que são menores do que o ponto de pivô estão à esquerda e todos os elementos que são maiores do que o ponto de pivô estão à direita. Suponha que a matriz tem estes dez valores:
38 17 58 22 69 31 88 28 86 12
Aqui, o ponto de pivô é de 38, ea tarefa da etapa de particionamento é reorganizar a matriz para algo como isto:
17 12 22 28 31 38 88 69 86 58
Observe que os valores ainda estão fora de ordem. A matriz, no entanto, foi dividido em torno do valor 38: Todos os valores que são menos do que 38 estão à esquerda de 38, e todos os valores que são maiores do que 38 são para a direita de 38.
Agora você pode dividir a matriz em duas partições no valor de 38 e repita o processo para cada lado. O valor em si pivot vai com a partição de esquerda, de modo a partição esquerda é esta:
17 12 22 28 31 38
Desta vez, a etapa de particionamento pega 17 como ponto de pivô e reorganiza os elementos da seguinte forma:
12 17 22 28 31 38
Como você pode ver, esta parte da matriz é classificada agora. Infelizmente, Quicksort não percebe que, neste ponto, por isso demora mais alguns recursions para ter certeza. Mas esse é o processo básico.