Reorganize os elementos da tabela para que os elementos da tabela satisfaçam o processo de aumentar ou diminuir por palavra-chave

Se houver dois elementos Ri e Rj no algoritmo de classificação, suas palavras-chave correspondentes keyi=keyj, e Ri está na frente de Rj antes da classificação, se após a classificação, Ri ainda estiver na frente de Rj, este algoritmo é estável. Caso contrário, é instável.

A estabilidade não pode medir a qualidade de um algoritmo

Divida a sequência em duas partes, ordenada e não ordenada, e insira os bits apropriados na parte ordenada a cada vez.

princípio

desempenho

Classificação por inserção direta usando pesquisa binária

Número de comparações de elementos

desempenho

A tabela de classificação é dividida em várias subtabelas, cada subtabela é inserida diretamente na classificação e, finalmente, toda a classificação por inserção é executada.

desempenho

Começando do início, compare cada par de elementos adjacentes e mova-os para trás se forem maiores. Após a comparação, o elemento maior estará no final. Repita o processo acima, não melhor que o maior, e continue repetindo para obter a sequência.

desempenho

1. Primeiro, pegue um número da sequência como número base. 2. Processo de particionamento: coloque todos os números maiores que este número à sua direita e coloque todos os números menores ou iguais a ele à sua esquerda. 3. Repita a segunda etapa para os intervalos esquerdo e direito até que haja apenas um número em cada intervalo.

O pior caso é que cada vez que o número do meio selecionado seja o maior ou o menor elemento da sequência atual. A classificação rápida de uma tabela de dados de comprimento n requer n divisões, tornando a complexidade de tempo de todo o algoritmo de classificação O (n ^ 2)

desempenho

Cada vez o menor é selecionado e trocado pela posição especificada.

Número de comparações n(n-1)/2 Complexidade de tempo O(n^2)

desempenho

amontoar

organizar

Construa uma pilha

inserir

excluir

A tabela a ser classificada contém n registros, que podem ser considerados como n subtabelas ordenadas. Cada subtabela tem comprimento 1 e, então, são classificadas em pares. Obtenha listas ordenadas ⌈n/2⌉ com comprimento 2 ou 1 e, em seguida, mescle-as em dois poços. Repita isso até que sejam mescladas em uma lista ordenada de comprimento n. Observe a diferença entre mesclagem recursiva e mesclagem não recursiva

desempenho