A classificação rápida é encontrar um elemento (originalmente você pode encontrar um) como referência (pivô) e, em seguida, particionar a matriz para que o valor do elemento à esquerda da referência não seja maior que o valor de referência e o valor do elemento à direita da referência não é menor que o valor de referência. Classificação recursivamente rápida, ajuste os outros elementos N-1 na posição correta após a classificação. Finalmente, cada elemento está na posição correta após a classificação e a classificação é concluída. Portanto, o algoritmo principal do algoritmo de classificação rápido é a operação de particionamento, ou seja, como ajustar a posição da referência e ajustar a posição final do benchmark de retorno para dividir e conquistar a recursão.
O algoritmo para classificação rápida é:
1) Defina duas variáveis i e j, quando a classificação começar: i = 0, j = n-1;
2) Use o primeiro elemento da matriz como os principais dados e atribua -os à chave, ou seja, key = a [0];
3) Comece de J para pesquisar adiante, isto é, comece por trás para pesquisar adiante (j--), encontre o primeiro valor a [j] menor que a chave e troque a [j] e um [i];
4) Comece de i para pesquisar para trás, ou seja, comece da frente para trás (i ++), encontre o primeiro a [i] maior que a chave e troque de [i] e um [j];
5) Repita as etapas 3 e 4 até i = j; 4 não é maior que a alteração da chave dos valores de J e I para que J = J-1, I = I+1 até que seja encontrado. permanece inalterado.
Deixe -me dar um exemplo, isso pode não ser fácil de entender. Suponha que a sequência a ser classificada é
A cópia do código é a seguinte:
pacote com.zc.manythread;
importar java.util.random;
/**
* Classificação rápida
* Administrador @Author
*
*/
classe pública QSORT {
int [] data;
Public Qsort (int [] data) {
this.date = date;
}
/**
* Função de troca
* @param a
* @param i
* @param j
*/
troca de vazio privado (int a [], int i, int j) {
int t;
T = a [i];
a [i] = a [j];
a [j] = t;
}
/***************************
* Função de classificação
* @param a
* @param lo0
* @param hi0
* @retornar
*/
int [] QuickSort (int a [], int lo0, int hi0) {// O método de divisão e tratamento é dividir a matriz em um [lo0..q-1] e um [q+1..hi0]
int lo = lo0;
int hi = hi0;
int mid;
if (hi0> lo0) {
mid = a [(hi0+lo0)/2];
while (lo <= hi) {
while ((lo <hi0) && (a [lo] <mid)) ++ lo;
while ((hi> lo0) && (a [hi]> mid)) - -hi;
if (lo <= hi) {
trocar (a, lo, oi);
++ lo;
--oi;
}
}
if (lo0 <hi) {
Quicksort (a, lo0, oi);
}
if (lo <hi0) {
Quicksort (a, lo, hi0);
}
}
retornar a;
}
/********************
*
* Crie dados de matriz duplicados
**********************/
private static int [] criado (int conting) {
int [] dados = new int [count];
for (int i = 0; i <data.length; i ++) {
dados [i] = (int) (math.random ()*contagem);
}
retornar dados;
}
/**
* Nenhum dado de matriz duplicado
* @param count
* @retornar
*/
private static int [] criateate1 (int count) {
int [] dados = new int [count];
Rand aleatório = novo aleatório ();
booleano [] bool = novo booleano [100];
int num = 0;
for (int i = 0; i <contagem; i ++) {
fazer {
// Se o número gerado for o mesmo, continue a fazer um loop
num = rand.nextint (100);
} while (bool [num]);
bool [num] = true;
dados [i] = num;
}
retornar dados;
}
/************ Função principal *********************/
public static void main (string [] args) {
final int contagem = 10;
int [] data = criateate1 (contagem);
para (int n: dados) {
System.out.print (n+"/t");
}
QSORT data1 = novo QSORT (dados);
System.out.println ();
int [] a = data1.quicksort (dados, 0, contagem-1);
para (int n: a) {
System.out.print (n+"/t");
}
}
}
Os resultados são os seguintes:
O acima é todo o conteúdo descrito neste artigo.