Java Quicksort Princípio e Código de Implementação

O Quicksort é um algoritmo de classificação mais usado e mais eficiente e é frequentemente mencionado durante o processo de entrevista. Vamos explicar seus princípios em detalhes e fornecer uma implementação da versão Java.

Ideia rápida de classificação:

Duas peças independentes são divididas classificando o conjunto de elementos de dados RN em uma viagem. Uma parte da palavra -chave é menor que a outra parte. Em seguida, classifique as palavras -chave das duas partes, uma a uma até que haja apenas um elemento independente, e toda a coleção de elementos está em ordem.

O processo de classificação rápida - o método de cavar orifícios e preencher números (esse é um nome muito vívido), para um conjunto de elementos r [baixo ... alto], primeiro pegue um número (geralmente r [baixo]) como uma referência e r [baixo] reorganiza todos os elementos como referência.

Todos aqueles menores que r [baixo] são colocados na frente, todos maiores que r [baixo] são colocados na parte traseira e, em seguida, r [baixo] é usado como limite e r [baixo ... alto] é dividido em dois subconjuntos e depois dividido. Até baixo> = alto.

Por exemplo: O processo de realização de uma classificação rápida de r = {37, 40, 38, 42, 461, 5, 7, 9, 12} é o seguinte (Nota: A tabela a seguir de elementos descritos abaixo começa a partir de 0):

Comece a selecionar a base da base = 37, a tabela abaixo é baixa = 0, alta = 8, começando de alta = 8, se r [8] <base, escreva o conteúdo na posição alta em r [baixo] e depois alto A posição está vazia, baixa = baixa +1;

Comece a sondar de baixo, uma vez que baixo = 1, r [baixo]> base, escreva r [baixo] para r [alto], alto = alto -1;

Low <High é detectado, então a primeira classificação rápida ainda precisa continuar:

Nesse momento, baixo = 1, alto = 7, porque r [alto] <base, r [alta] é gravado em r [baixo], baixo = baixo + 1;

Inicie a detecção de baixa, baixa = 2, r [baixa]> base, então r [baixo] é escrito para r [alto], alto = alto-1;

Continue a detectar baixo é menor que alto

Nesse momento, baixo = 2, alto = 6, da mesma forma, r [alto] <base, escreva r [alto] para r [baixo], baixo = baixo+1;

Continue a detectar de baixo, baixo = 3, alto = 6, r [baixo]> base, escreva r [baixo] para r [alto], alto = alto-1;

Continue a detectar que o baixo é menor que o alto

Nesse momento, baixo = 3, alto = 5, da mesma forma, r [alto] <base, escreva r [alto] em r [baixo], baixo = baixo +1;

Continue a investigar de baixo, baixo = 4, alto = 5, porque r [baixo]> base, escreva r [baixo] em r [alto], alto = alto -1;

Nesse momento, Low == High == 4 é detectado;

Em seguida, faça uma classificação rápida das subseqüências rs1 = {12,9,7,5} e rs2 = {461,42,38,40} até que haja apenas um elemento no RSI ou nenhum elemento.

(Nota: No formulário acima, você pode ver que existem alguns dados duplicados na classificação (nenhum dado duplicado nos dados originais). Isso ocorre porque os dados nesse local não são limpos. Observamos os dados da memória Bloco em um horário específico.

Implementação de Java de classificação rápida:

A cópia do código é a seguinte:

private estático booleano isEmpty (int [] n) {

retornar n == null || n.length == 0;

}

// ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////idé ///

/**

* Algoritmo de classificação rápida IDEA - Método de cavar orifícios e encher:

*

* @param n Array para ser classificado

*/

public static void Quicksort (int [] n) {

If (isEmpty (n))

retornar;

Quicksort (n, 0, n.length - 1);

}

public static void Quicksort (int [] n, int l, int h) {

If (isEmpty (n))

retornar;

if (l <h) {

int pivot = partition (n, l, h);

Quicksort (N, L, Pivot - 1);

Quicksort (n, pivô + 1, h);

}

}

Partição privada estática int (int [] n, int start, int end) {

int tmp = n [start];

while (start <end) {

while (n [end]> = tmp && start <end)

fim--;

if (start <end) {

n [start ++] = n [end];

}

while (n [start] <tmp && start <end)

start ++;

if (start <end) {

n [end--] = n [start];

}

}

n [start] = tmp;

Start de retorno;

}

Há uma função como esta no código:

A cópia do código é a seguinte:

public static void QuicksortSortSwap (int [] n, int l, int h)

Esta função pode ser implementada para classificar elementos de dados no conjunto de elementos entre posições específicas de L e H.

Isso é tudo para classificação rápida.