Refere-se a uma classificação em que todos os elementos são armazenados na memória durante a classificação

Refere-se a um processo de classificação em que todos os elementos não podem ser armazenados na memória ao mesmo tempo durante a classificação e são constantemente movidos entre a memória interna e externa durante o processo de classificação.

De L[2]~L[n-1], cada vez que o elemento a ser classificado L[i] é inserido na sequência previamente classificada, e os elementos maiores que L[i] são movidos de volta na ordem (compare as arestas para frente, mova o elemento para trás)

Melhor: os elementos da tabela já estão ordenados

Pior: ordem inversa

média

Estabilizar

Tabelas lineares adequadas para armazenamento sequencial e armazenamento vinculado; quando é armazenamento vinculado, a posição do elemento especificado pode ser pesquisada da frente para trás (na verdade, a maioria dos algoritmos de classificação interna são adequados apenas para armazenamento sequencial)

Primeiro dobre ao meio para encontrar a posição onde o elemento será inserido e, em seguida, mova todos os elementos após o elemento a ser inserido uniformemente.

Número de comparações: (independentemente do estado inicial da tabela)

Número de movimentos: depende do estado inicial da tabela ordenada

Estabilizar

Aplica-se apenas a tabelas de sequência

Organize os elementos com um intervalo de d1 (etapa/incremento) em um grupo, divida a tabela de classificação em várias subtabelas, execute a classificação por inserção direta dentro de cada subtabela, reduza o incremento d2 e repita o processo acima até di =1 até

instável

Só é aplicável quando a tabela linear é armazenada sequencialmente (porque são utilizadas as características de acesso aleatório do armazenamento sequencial)

Compare os valores dos elementos adjacentes de trás para frente (ou de frente para trás). Se estiverem na ordem inversa, troque-os até que a sequência seja comparada. O resultado de cada rodada será trocar o menor elemento pelo primeiro. posição da sequência a ser ordenada (ou para o maior elemento). Os elementos são trocados para o final da coluna a ser ordenada), e este ciclo pode ser feito n-1 vezes.

Melhor (nenhuma troca ocorre na primeira passagem de classificação, salte diretamente do loop)

Pior (na ordem inversa)

Estabilizar

A subsequência gerada na classificação por bolha deve ser ordenada globalmente (diferente da inserção direta), e todos os elementos nela devem ser maiores ou menores que todos os elementos na subsequência não ordenada, e cada passagem de classificação colocará um elemento em sua posição final

Com base no método dividir e conquistar, cada vez que um determinado elemento pivô é tomado como referência, a sequência é dividida em duas subtabelas, a esquerda e a direita, e então classificada recursivamente nas subtabelas.

Pior (ordenado ou invertido)

Melhor (simétrico, ou seja, a sequência é dividida em partes iguais para cada benchmark)

instável

O algoritmo com melhor desempenho médio entre algoritmos de ordenação interna

Nenhuma subsequência ordenada é gerada durante o processo, mas cada operação de classificação colocará o elemento pivô (base) em sua posição final.

①Para classificação de mesclagem k-way, k buffers de entrada e 1 buffer de saída precisam ser alocados na memória

② Classifique internamente um total de N registros (usando um algoritmo de classificação interno) e gere r segmentos de mesclagem iniciais ordenados internamente (r=『N/L], L é o número de buffers de entrada na memória)

③Mesclando viagens S e rotas k,

Hora de ler e gravar na memória externa

Tempo necessário para classificação interna

Tempo de mesclagem interna

1) Aumente o número de caminhos de fusão k e só precisa de fusão balanceada multidirecional

2) Reduza o número de segmentos de mesclagem iniciais r

Para evitar que a mesclagem interna seja afetada pelo aumento de k, uma árvore perdedora é introduzida. Os k nós folha armazenam respectivamente os registros dos k segmentos de mesclagem atualmente participantes da comparação durante o processo de mesclagem. memorize as "falhas" nas subárvores esquerda e direita ", o nó raiz aponta para o número mínimo;

O número inicial de comparações é k-1. Depois disso, são necessários apenas "log2k] tempos de comparação para selecionar um valor mínimo.

Após a introdução da árvore perdedora, o número de comparações não tem nada a ver com k, mas à medida que k aumenta, o número de buffers de entrada pode ser aumentado. Se o espaço total de memória permanecer inalterado, a capacidade de cada buffer precisa ser reduzida para. reduzir o número de trocas de memória interna e externa aumentar.

Aumente o comprimento de cada segmento de mesclagem (mas não o comprimento fixo), reduzindo assim o número de segmentos de mesclagem

Deixe o arquivo inicial a ser classificado ser FI, o arquivo de saída do segmento de mesclagem inicial ser FO e a área de trabalho da memória ser WA (pode acomodar w registros)

1) Insira w registros do FI para o espaço de trabalho WA.

2) Selecione o registro com o valor mínimo da palavra-chave de WA e registre-o como registro MINIMAX.

3) Envie registros MINIMAX para FO.

4) Se FI não estiver vazio, insira o próximo registro de FI em WA.

5) Selecione o menor registro de palavra-chave de todos os registros em WA com palavras-chave maiores que o registro MINIMAX como o novo registro MINIMAX.

6) Repita 3)~5) até que nenhum novo registro MINIMAX possa ser selecionado em WA, obtendo assim um segmento de mesclagem inicial e enviando um sinalizador final do segmento de mesclagem para FO.

7) Repita 2)~6) até que WA esteja vazio. A partir disso, todos os segmentos iniciais mesclados são obtidos.

1) Cada segmento de mesclagem inicial corresponde a um nó folha, e o número de blocos contidos no segmento de mesclagem é o peso da folha.

2) Mesclar árvore WPL = a soma dos comprimentos de caminho ponderados de todos os nós folha na árvore

3) O número de E/S de disco durante o processo de mesclagem = WPL da árvore mesclada*2

1) Complemente o parágrafo virtual

2) Construa uma árvore k-ary Huffman

1) A classificação rápida é considerada o melhor método entre os métodos atuais de classificação interna baseados em comparação. Quando as palavras-chave a serem classificadas são distribuídas aleatoriamente, o tempo médio de classificação rápida é o mais curto.

2) A classificação heap requer menos espaço auxiliar do que a classificação rápida e não sofre o pior cenário que a classificação rápida pode ter; ambas as classificações são instáveis.

3) Se a classificação precisar ser estável e a complexidade de tempo for O (nlog2n), a classificação por mesclagem poderá ser usada.

A classificação por mesclagem bidirecional trata a lista a ser classificada como n sublistas (cada sublista tem comprimento 1) e, em seguida, as mescla recursivamente até que uma lista ordenada de comprimento n seja sintetizada.

eficiência de espaço

Eficiência de tempo

Estabilizar

Use a ideia de classificação de várias palavras-chave para lidar com palavras-chave lógicas únicas

Bit mais significativo primeiro (MSD)

Menos significativo primeiro (LSD)

A base r = 10 requer 10 filas em cadeia; cada palavra-chave tem 3 bits e requer três operações de "alocação" e "coleta".

eficiência de espaço

Eficiência de tempo

Estabilizar

A i-ésima classificação seleciona o elemento com a menor palavra-chave de L[i...n] e o troca por L[i]. Cada passagem pode determinar a posição final de um elemento.

Número de comparações: n(n-1)/2

Número de movimentos

instável

amontoar

Algoritmo de classificação

① Para uma árvore binária completa com n nós, comece a filtrar a partir do nó pai do último nó ("n/2]) e troque os nós pai e filho para torná-lo chamado de heap raiz grande (o nó pai pode continuar a vá para baixo) e, em seguida, filtre as subárvores enraizadas em cada nó ("n/2]~1)

②Depois de gerar o elemento superior do heap, troque o último elemento superior do heap pelo elemento superior do heap e, em seguida, troque recursivamente a ordem do elemento superior do heap pelo maior dos filhos.

Algoritmo de criação de heap raiz grande

Algoritmo de classificação de heap

Primeiro coloque o novo nó no final do heap e depois aponte-o para cima para a operação de ajuste

complexidade de tempo

eficiência de espaço

Eficiência de tempo

instável

Adequado para armazenamento sequencial (devido ao acesso aleatório)