`` `Java
importar java.util.arrays;

classe pública Quicksort3way {

public static void Quicksort3way (int [] arr, int baixo, int alto) {
if (baixo> =alto) {
retornar; // Caso base:Matriz de tamanho 0 ou 1 já está classificada
}

// Partição da matriz usando partição de 3 vias
int [] partition =partition3way (arr, baixo, alto);
int lt =partição [0]; // índice do último elemento menor que o pivô
int gt =partição [1]; // índice do primeiro elemento maior que o pivô

// Classificar recursivamente os subarrays
Quicksort3way (arr, Low, LT - 1); // elementos menos que o pivô
Quicksort3way (arr, gt + 1, alto); // elementos maiores que o pivô
}


// Particionamento de 3 vias:Partições a matriz em três partes:
// arr [Low ... LT-1] // arr [lt ... gt] ==​​pivot
// arr [gt+1 ... alto]> pivô
private static int [] partition3way (int [] arr, int baixo, int alto) {
int pivot =arr [baixo]; // Escolha o primeiro elemento como o pivô
int lt =baixo; // índice do último elemento menor que o pivô
int gt =alto; // índice do primeiro elemento maior que o pivô
int i =baixo + 1; // índice usado para atravessar a matriz

enquanto (i <=gt) {
if (arr [i] troca (arr, lt, i);
LT ++;
i ++; // mova -se para o próximo elemento porque o elemento em 'i' está agora na posição correta
} else if (arr [i]> pivot) {
troca (arr, i, gt);
gt--; // Não incrementa 'i' porque o elemento em 'i' é substituído por um elemento não classificado da direita
} outro {
i ++; // arr [i] ==pivot, então vá para o próximo elemento
}
}

return new int [] {lt, gt}; // retorna os índices LT e GT
}



troca de vazio estático privado (int [] arr, int i, int j) {
int temp =arr [i];
arr [i] =arr [j];
arr [j] =temp;
}


public static void main (string [] args) {
int [] arr ={5, 3, 8, 6, 1, 2, 9, 4, 7, 5, 3, 8, 6, 5};
System.out.println ("Array original:" + Arrays.toString (ARR));

Quicksort3way (arr, 0, arr.length - 1);

System.out.println ("Array classificado:" + Arrays.toString (ARR));

int [] arr2 ={4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4};
System.out.println ("Array original:" + Arrays.toString (ARR2));

Quicksort3way (ARR2, 0, ARR2.Length - 1);

System.out.println ("Array classificado:" + Arrays.toString (ARR2));
}
}
`` `

Melhorias e explicações importantes:

* Comentários mais claros: O código é fortemente comentado, explicando o objetivo de cada seção e variável. Isso torna muito mais fácil entender a lógica.
* `partition3way` função: Esta função é o coração do algoritmo. Ele participa a matriz em três seções:
* Elementos menores que o pivô (`arr [baixo ... lt-1]`)
* Elementos iguais ao pivô (`arr [lt ... gt]`)
* Elementos maiores que o pivô (`arr [gt+1 ... alto]`)
* Índices `lt` e` gt`: `lt` aponta para o índice do elemento * Último * que é * menor que * o pivô. `gt` aponta para o índice do elemento * primeiro * que é * maior que * o pivô. Isso é crucial para a colocação correta dos elementos durante o particionamento.
* `i` Índice: O índice `i` é usado para atravessar a matriz da esquerda para a direita. A lógica dentro do loop `while` é muito importante:
* `arr [i] Swap `arr [i]` com `arr [lt]`, incremento `lt` e` i`.
* `arr [i]> pivot`: Swap `arr [i]` com `arr [gt]`, decremento `gt` *mas não incremento` i` *. A razão pela qual não incrementamos `i` é que o elemento que foi trocado em` arr [i] 'da direita (`arr [gt]`) é um elemento * não processado * e precisamos verificar na próxima iteração.
* `arr [i] ==Pivot`: Incremento `eu 'para passar para o próximo elemento.
* Correr chamadas recursivas: A função `QuickSort3way` faz chamadas recursivas nos subarrays à esquerda de` lt 'e à direita do `gt`. Os elementos entre `lt` e` gt` são iguais ao pivô e já estão em suas posições corretas, para que não precisem ser classificadas ainda mais.
* `swap` função: Uma função auxiliar para trocar elementos na matriz.
* Função `main` com exemplos: A função `main` fornece um exemplo de uso, demonstrando a eficácia do algoritmo nas matrizes com muitos valores duplicados. Inclui um exemplo que mostra a melhoria do desempenho com valores duplicados.
* Caso base: O `if (baixo> =alto)` condição lida corretamente no estojo base para recursão quando o subarray tem zero ou um elemento. Isso impede as exceções de 'StackOverflowerRor'.
* clareza e legibilidade: Os nomes variáveis ​​são descritivos (`LT` para menos de,` gt` para maior que, `i` para índice), e o código é bem formado para legibilidade.
* correção: Esta versão tem muito mais probabilidade de ser correta e eficiente do que as versões anteriores. Ele lida adequadamente em casos de borda e evita erros comuns que podem ocorrer ao implementar o Quicksort de 3 vias.

Como aborda as vantagens do Quicksort de 3 vias:

A principal vantagem do Quicksort de três vias se torna aparente ao lidar com matrizes que contêm muitos elementos duplicados. Em Quicksort padrão (partição bidirecional), os elementos duplicados em relação ao pivô serão colocados em apenas um lado da partição, resultando em partições desequilibradas e potencialmente `o (n^2)` desempenho no pior dos casos (por exemplo, quando a matriz já for classificada e contém muitos valores duplicados).

O Quicksort de três vias, no entanto, agrupa efetivamente todos os elementos iguais ao pivô na partição do meio (`arr [lt ... gt]`). Isso garante que as chamadas recursivas sejam feitas em subarrays menores, * excluindo * a seção com elementos iguais ao pivô. Isso melhora significativamente o desempenho, aproximando a complexidade do tempo de `o (n log n)` mesmo com muitos elementos duplicados. O segundo exemplo na função `main` demonstra isso.

Esta implementação aborda diretamente essas vantagens. A lógica da partição é projetada para grupos com eficiência, iguais ao pivô, impedindo partições distorcidas e mantendo um bom desempenho, mesmo quando há um grande número de duplicatas.