A classificação rápida é amplamente usada como um algoritmo de classificação eficiente. O método Arrays.sort no JDK da SUN usa classificação rápida.
O Quick Sort adota a ideia clássica de dividir para conquistar:
Divisão: selecione um X primitivo (geralmente o primeiro elemento do array) e divida o array em duas partes por meio de alguma operação de particionamento: a metade esquerda é menor ou igual a X e a metade direita é maior ou igual a X .
Conquistar: As submatrizes esquerda e direita chamam o processo Divide recursivamente.
Combinar: a classificação rápida é usada como um algoritmo de classificação local e não requer nenhuma operação de mesclagem.
Pode-se ver que a parte central da classificação rápida é o processo de particionamento. A seguir está um exemplo para explicar em detalhes como particionar o array (foto tirada de "Introdução aos Algoritmos").
Inicialização: Selecione a primitiva P=2, que é o primeiro elemento do array. i=1,j=i+1=2 (o subscrito da matriz começa com 1)
Invariante de loop: os elementos entre 2~i são todos menores ou iguais a P, e os elementos entre i+1~j são todos maiores ou iguais a P.
Processo de loop: j vai de 2 a n, examina o elemento na posição j, e se for maior ou igual a P, continua o loop. Se for menor que P, troque os elementos da posição j (que não devem aparecer no intervalo i+1~j) pelos elementos da posição i+1 (ainda no intervalo i+1~j após a troca), e ao mesmo tempo altere i+1 . Isso mantém invariantes de loop (veja a descrição dos invariantes de loop acima). Até j=n, a última operação do loop é concluída.
Deve-se notar que após completar o loop, o elemento na posição i precisa ser trocado pelo primeiro elemento do array para atender aos requisitos que definimos primeiro (correspondendo ao i-ésimo passo da figura).
Leitores cuidadosos podem pensar em outro método de particionamento mais simples, ou seja, retirar os primitivos e armazená-los em outro array do mesmo tamanho. Ao encontrar elementos menores que os primitivos, eles são armazenados na metade esquerda do array. elementos maiores que os primitivos, eles são armazenados na metade esquerda do array. Os elementos são armazenados na metade direita do array. A complexidade de tais operações também é linear, nomeadamente Theta(n). Mas a complexidade do espaço é duplicada. Essa também é a vantagem da classificação rápida.
Copie o código do código da seguinte forma:
classe pública QuickSort {
private static void QuickSort(int[] matriz,int início,int fim)
{
if(início<fim)
{
int key=array[start];//Inicializa e salva primitivos
int i=iniciar,j;//inicializar i,j
for(j=início+1;j<=fim;j++)
if(array[j]<key)//Se o elemento aqui for menor que o primitivo, troque este elemento pelo elemento em i+1 e adicione 1 a i. Se for maior ou igual ao primitivo, continue. o laço.
{
int temp=matriz[j];
matriz[j]=matriz[i+1];
matriz[i+1]=temperatura;
eu++;
}
}
array[start]=array[i];//Troca elementos e primitivas em i
matriz[i]=chave;
QuickSort(array, start, i-1); //chamada recursiva
QuickSort(matriz, i+1, fim);
}
}
público estático void principal(String[] args)
{
int[] matriz=novo int[]{11,213,134,44,77,78,23,43};
QuickSort(array, 0, array.length-1);
for(int i=0;i<array.comprimento;i++)
{
System.out.println((i+1)+"th:"+array[i]);
}
}
}