Um tipo de melhoria na classificação borbulhante é que, se a sequência de registro inicial for ordenada ou basicamente ordenada por palavras -chave, ela degenerará na classificação borbulhante. O princípio da recursão é usado e seu desempenho médio é o melhor entre todos os métodos de classificação da mesma ordem de magnitude o (n longn). Em termos de tempo médio, atualmente é considerado o melhor método de classificação interna.
A idéia básica é: divida os dados a serem classificados em duas partes independentes, localizando, e todos os dados em parte são menores do que todos os dados da outra parte e depois classificam rapidamente essas duas partes dos dados de acordo com este método Todo o processo de classificação pode ser executado recursivamente para alcançar todos os dados, tornando -se uma sequência ordenada.
Três ponteiros: o primeiro ponteiro é chamado de ponteiro de pivotkey (pivô), o segundo ponteiro e o terceiro ponteiro são o ponteiro esquerdo e o ponteiro direito, respectivamente, apontando para o valor mais à esquerda e o valor mais à direita. O ponteiro esquerdo e o ponteiro direito se aproximam de ambos os lados para o meio ao mesmo tempo. Gire para a extremidade superior.
São necessárias duas funções:
① Função recursiva Public Static Void Quicksort (int [] n, int esquerda, int à direita)
② Função do segmento (uma função de classificação rápida) Public static int partition (int [] n, int esquerdo, int à direita)
Java Código fonte (executado com sucesso):
A cópia do código é a seguinte:
pacote testsortalgorithm;
classe pública Quicksort {
public static void main (string [] args) {
int [] array = {49,38,65,97,76,13,27};
Quicksort (Array, 0, Array.Length - 1);
for (int i = 0; i <Array.length; i ++) {
System.out.println (Array [i]);
}
}
/*Primeiro escreva o algoritmo como protótipo de dados de acordo com a matriz e depois escreva o algoritmo de escalabilidade. Array {49,38,65,97,76,13,27}
* */
public static void Quicksort (int [] n, int esquerda, int à direita) {
int pivot;
if (esquerda <direita) {
// pivô como pivô, o elemento menor está à esquerda e o elemento maior está à direita
pivô = partição (n, esquerda, direita);
// Chame recursivamente Classificação rápida nas matrizes esquerda e direita até que o pedido esteja completamente correto
Quicksort (n, esquerda, pivô - 1);
Quicksort (n, pivô + 1, à direita);
}
}
public static int partition (int [] n, int esquerda, int à direita) {
int pivotkey = n [esquerda];
// O pivô nunca mudará depois de ser selecionado, e acabará no meio, com pequena frente e grande traseira
enquanto (esquerda <direita) {
while (esquerda <direita && n [direita]> = pivotkey) - -right;
// Mova o elemento menor que o pivô para a extremidade baixa.
n [esquerda] = n [direita];
while (esquerda <direita && n [esquerda] <= pivotkey) ++ esquerda;
// Mova o elemento maior que o pivô para a extremidade alta.
n [direita] = n [esquerda];
}
// Quando esquerda == Right, complete uma rápida viagem de classificação.
n [esquerda] = Pivotkey;
retornar à esquerda;
}
}