princípio
A classificação de bolhas é provavelmente um algoritmo que todos os programadores podem usar e também é um dos algoritmos mais familiares.
Suas idéias não são complicadas:
Suponha que o Array Arr [] agora seja classificado e possui n elementos.
1. Se n = 1: Obviamente, não há necessidade de fazer fila. (De fato, essa discussão parece ser desnecessária)
2. Se n> 1:
(1) Começamos com o primeiro elemento e comparamos a cada dois elementos adjacentes. Se o elemento anterior for maior que o próximo, o primeiro será definitivamente classificado para trás no resultado final. Então, trocamos esses dois elementos. Em seguida, compare os próximos dois elementos adjacentes. Dessa forma, até que o último par de elementos seja comparado, a primeira rodada de classificação é concluída. É certo que o último elemento deve ser o maior da matriz (porque o relativamente grande é colocado na parte traseira toda vez).
(2) Repita o processo acima, desta vez não precisamos considerar o último porque ele já está organizado.
(3) Então, até que haja apenas um elemento, o elemento deve ser o menor e, em seguida, nossa classificação pode terminar. Aparentemente, a classificação N-1 foi realizada.
No processo acima, toda vez (ou "roda" é classificada, um número vai lentamente "flutuar" de uma certa posição para a posição final (desenhe um diagrama esquemático e desenhe a matriz verticalmente), como bolhas, para que seja chamado de "método de classificação de bolhas".
Implementação de código:
classe pública bubblesort {public static void main (string [] args) {int score [] = {67, 69, 75, 87, 89, 90, 99, 100}; para (int i = 0; i <score.length -1; i ++) {// não apenas faz o pedido para (int j = 0; j <score.length -i -1; j ++) {// classificar o número de intervalos não ordenados [0 ...... comprimento -i (o intervalo j é muito crítico, esse intervalo não é realmente um pouco gradualmente na graduação) se o que é realmente um rigoroso [0). posterior int temp = pontuação [j]; pontuação [j] = pontuação [j + 1]; pontuação [j + 1] = temp; }} System.out.print ("Th" + (i + 1) + "Resultado de classificação da sequência:"); for (int a = 0; a <score.length; a ++) {System.out.print (pontuação [a]+"/t"); } System.out.println (""); } System.out.print ("Resultado da classificação final:"); for (int a = 0; a <score.length; a ++) {System.out.print (pontuação [a]+"/t"); }}}
Desempenho/complexidade do algoritmo
Ignoramos o tempo em que as variáveis de loop são aumentadas e inicializadas automaticamente. Primeiro analise o número de comparações do algoritmo. É fácil ver que a classificação de bolhas acima, sem qualquer melhoria, será realizada nas rodadas N-1, independentemente dos dados de entrada, e o número de vezes que cada rodada de classificação precisa ser comparada diminuindo de N-1 para 0. Então, o número total de comparações é (n-1)+(n-2)+...+2+1 = (n-1) N/2≈ (n 2)/2)/2. (Como não sei como fazer quadrados aqui, aqui, eu uso n^2 para representar quadrados, o mesmo abaixo)
Vamos dar uma olhada no número de tarefas. A tarefa aqui refere -se à operação de troca. Para o código acima, 1 Exchange é igual a três atribuições. Como não é necessário trocar, o número de operações de atribuição está relacionado aos dados de entrada. Na melhor das hipóteses, ou seja, quando a ordem é no início, o número de atribuições é 0. Na pior das hipóteses, o número de atribuições é (n-1) n/2. Supondo que os dados de entrada seja a distribuição média (ou "completamente aleatória"), cerca de metade do número de trocas. A partir dos resultados acima, podemos obter o caso médio, com o número de atribuições sendo 3/2 * (n^2)/2 = 3/4 * (n^2).
Em resumo, em qualquer caso, a complexidade do espaço de classificação da bolha (espaço extra) é sempre O (1).
melhorar
A complexidade do tempo ideal é mostrada quando os dados são completamente ordenados, que é O (n). Em outros casos, é quase sempre O (n^2). Portanto, o algoritmo tem um desempenho melhor quando os dados são basicamente ordenados.
No entanto, como o código acima pode ter complexidade O (n)? De fato, como o acima menciona as idéias básicas, é apenas o caso mais simples. Para fazer com que o algoritmo tenha complexidade O (n) no melhor caso, algumas melhorias precisam ser feitas. O código aprimorado é:
public static void bubblesort (int [] arr) {int temp = 0; troca booleana; for (int i = arr.length -1; i> 0; --i) {// O comprimento de cada classificação precisa ser trocado = false; for (int j = 0; j <i; ++ j) {// do primeiro elemento para o elemento i-sh if (arr [j]> arr [j +1]) {temp = arr [j]; arr [j] = arr [j + 1]; arr [j + 1] = temp; swap = true; }} // loop j if (swap == false) {break; }} // loop i} // Método BubblesortDe fato, como a classificação de bolhas dificilmente é usada no caso de grandes quantidades de dados, as variáveis booleanas adicionadas ao usar dados pequenos causarão uma sobrecarga adicional. Então, pessoalmente, acho que o algoritmo melhorado acima é apenas puramente teórico. Geralmente, apenas escreva o anterior, Bubbling Classing.
Estabilidade do algoritmo
É fácil ver que, quando os elementos vizinhos são iguais, não precisamos trocar suas posições, para que o tipo de bolha seja um tipo estável.
Algoritmo cenários aplicáveis
A idéia de classificação de bolhas é simples e o código é simples, o que é especialmente adequado para classificar pequenos dados. No entanto, devido à alta complexidade do algoritmo, ele não é adequado para uso quando o volume de dados é grande. Se você precisar usá -lo quando houver mais dados, é melhor melhorar o algoritmo, como a seleção do método de classificação.