Um algoritmo é um conjunto de regras bem definidas usadas para resolver um problema em um número limitado de etapas. Simplificando, é o processo de resolução de problemas por computador. Neste processo, quer você esteja formando uma ideia para resolver um problema ou escrevendo um programa, você está implementando um determinado algoritmo. O primeiro é um algoritmo implementado por raciocínio e o último é um algoritmo implementado por operação.
Um algoritmo deve ter as seguintes cinco características importantes:
1. Finitude: Um algoritmo deve garantir que termina após a execução de um número finito de etapas;
2. Exatidão: Cada etapa do algoritmo deve ser claramente definida;
3. Entrada: Um algoritmo possui 0 ou mais entradas para descrever a situação inicial do operando;
4. Saída: Um algoritmo possui uma ou mais saídas para refletir os resultados do processamento dos dados de entrada. Um algoritmo sem saída não tem sentido;
5. Viabilidade: Em princípio, o algoritmo pode ser executado com precisão e pode ser concluído por pessoas que usam papel e caneta para realizar um número limitado de operações.
Merge sort (MERGE SORT) é outro tipo de método de classificação diferente. O significado da fusão é mesclar duas ou mais sequências de dados ordenadas em uma nova sequência de dados ordenada, por isso também é chamado de algoritmo de mesclagem. Sua ideia básica é assumir que a matriz A tem N elementos, então a matriz A pode ser considerada como consistindo de N subsequências ordenadas, cada subsequência tem um comprimento de 1 e então mesclada dois por dois para obter uma N/2 Uma subsequência ordenada de o comprimento 2 ou 1 é então mesclado dois por dois e isso é repetido até que uma sequência ordenada de dados de comprimento N seja obtida. Esse método de classificação é chamado de classificação por mesclagem bidirecional.
Por exemplo, a matriz A possui 7 dados, que são: 49 38 65 97 76 13 27. Em seguida, o processo de operação de uso do algoritmo de classificação por mesclagem é mostrado na Figura 7:
Valor inicial[49][38][65][97][76][13][27]
Visto como consistindo em 7 subsequências de comprimento 1. Após a primeira fusão [38 49] [65 97] [13 76] [27]
Visto como consistindo em 4 subsequências de comprimento 1 ou 2. Após a segunda fusão [38 49 65 97] [13 27 76]
Visto como consistindo em 2 subsequências de comprimento 4 ou 3. Após a terceira fusão [13 27 38 49 65 76 97]
Figura 6 Diagrama do processo do algoritmo de classificação por mesclagem A operação principal do algoritmo de mesclagem é mesclar duas sequências ordenadas adjacentes em uma matriz unidimensional em uma sequência ordenada. O algoritmo de fusão também pode ser implementado usando um algoritmo recursivo, que é relativamente simples na forma, mas tem pouca praticidade.
O número de mesclagens no algoritmo de mesclagem é uma quantidade muito importante. De acordo com os cálculos, quando há de 3 a 4 elementos na matriz, o número de mesclagens é 2, quando há de 5 a 8 elementos, o número de mesclagens é 3. , e quando há 9 a Quando há 16 elementos, o número de fusões é 4. De acordo com esta regra, quando há N subsequências, pode-se inferir que o número de fusões é
X (2>=N, o menor X que atende à subcondição).
Descrição do algoritmo de bolha:
Antes de explicar o algoritmo de classificação por bolha, vamos primeiro apresentar um algoritmo que coloca o maior número entre 10 números (na matriz A) na última posição. O algoritmo é descrito da seguinte forma:
(1) Do array A[1] a A[10], compare dois números adjacentes em pares. Ou seja, A[1] é comparado com A[2], e após a comparação, A[2] é comparado com A[3],...e finalmente A[9] é comparado com A[10].
(2) Durante cada comparação, se o número anterior for maior que o último, os dois números serão trocados, ou seja, o número maior será movido para trás e o número menor será movido para a frente. Por exemplo, na primeira comparação, se A[1] for maior que A[2], os valores de A[1] e A[2] são trocados. A figura abaixo usa 6 dados para ilustrar o algoritmo acima.
Suponha que os 6 dados sejam: A[]=5 7 4 3 8 6
Um[1] Um[2] Um[3] Um[4] Um[5] Um[6]
5 7 4 3 8 6 Na primeira vez, A[1]=5 e A[2]=7 são comparados, 7>5, nenhuma troca é realizada.
5 7 4 3 8 6 Na segunda vez, A[2]=7 e A[3]=4 são comparados, 4<7, troca.
Então os dados após a segunda comparação são 5 4 7 3 8 6
5 4 7 3 8 6 Na terceira vez, A[3]=7 e A[4]=3 são comparados, 3<7, troca.
Então os dados após a terceira comparação são 5 4 3 7 8 6
5 4 3 7 8 6 Na quarta vez, A[4]=7 e A[5]=8 são comparados, 8>7, nenhuma troca é realizada.
5 4 3 7 8 6 Na quinta vez, A[6]=6 e A[5]=8 são comparados, 6<8, troca.
Então o quinto e último resultado é
5 4 3 7 6 8
************************************************** * *****
Descrição do algoritmo de classificação por seleção:
Antes de apresentar o método de classificação por seleção, vamos apresentar um algoritmo que coloca o menor número na primeira posição. Claro, você também pode usar o método de classificação por bolha mencionado acima. Agora usamos um novo algoritmo: Sua ideologia orientadora não está em um. apresse-se para mudar de posição no início, mas comece com A[1] começa a verificar um por um. Para ver qual número é o menor, anote a posição P do número. Após a conclusão da varredura, troque A[P] e A[1]. [1] a A[10] é movido para a posição frontal. As etapas do algoritmo são as seguintes:
1) Primeiro, suponha que o número em A[1] seja o menor e observe a posição P=1 neste momento;
2) Compare A[P] e A[I] em sequência (I muda de 2 para 10, durante cada comparação, se o número em A[I] for menor que o número em A[P], então I O valor). é atribuído a P, de modo que P sempre aponta para a posição do menor número atualmente escaneado, ou seja, A[P] é sempre igual ao menor número de todos os números escaneados. Após comparar um por um, P aponta para a posição do menor número entre os 10 números, ou seja, A[P] é o menor número entre os 10 números;
3) Inverta os números de A[P] e A[1], então o menor número ficará em A[1], ou seja, na frente.
Se você repetir esse algoritmo agora, mas cada vez que ele for repetido, o intervalo da série que está sendo comparada será movido para trás uma posição. Ou seja, na segunda comparação, o intervalo vai do 2º número ao enésimo número. Encontre a posição P do menor número dentro desse intervalo e, em seguida, troque A[P] e A[2], de modo que a partir do 2º. O menor número do início ao enésimo número está em A [2] for bem-sucedido, a terceira vez é encontrar o menor número do 3º ao enésimo número e, em seguida, trocar A[P] e A[3]... Depois de repetir este processo N-1 vezes, basta organizar os N números na matriz A, de pequeno a grande. Este método de classificação é a classificação por seleção.
************************************************** ****************
Descrição do algoritmo de classificação de inserção:
Ao aprender os dois métodos acima, você pode entender a ideia básica de classificação e também pode organizar qualquer array não ordenado de grande para pequeno (ordem decrescente) ou de pequeno para grande (ordem crescente). Agora suponha que exista uma sequência de dados já ordenada e seja necessário inserir um número nessa sequência de dados já organizada, mas é necessário que a sequência de dados ainda esteja ordenada após a inserção. Neste momento, um novo método de classificação irá. ser usado - Método de classificação por inserção, a operação básica da classificação por inserção é inserir um dado nos dados ordenados que foram classificados, de modo a obter um novo dado ordenado com o número mais um.
Pergunta: Existem N dados na matriz A, organizados em ordem de pequeno para grande. Insira um número X e insira o valor de X na matriz A, de modo que a matriz A inserida ainda esteja organizada em ordem de pequeno para grande. .
Então o algoritmo para resolver este problema é:
1) Encontre a posição onde X deve ser inserido comparando o tamanho, se deve ser colocado na I-ésima posição;
2) Mover todos os elementos do array começando em I (incluindo I) uma posição para trás, ou seja, A[I+1]:=A[I];
A classificação rápida é uma melhoria na classificação por bolha. Sua idéia básica é dividir os dados a serem classificados em duas partes independentes por meio de classificação unidirecional. Todos os dados em uma parte são menores do que todos os dados na outra parte e, em seguida, as duas partes dos dados são classificadas sequencialmente. Para uma classificação rápida, todo o processo de classificação pode ser executado recursivamente, de modo que todos os dados se tornem uma sequência ordenada.
Suponha que a matriz a ser classificada seja A[1]...A[N]. Primeiro, selecione aleatoriamente um dado (geralmente os primeiros dados) como os dados principais e, em seguida, coloque todos os números maiores que ele na frente dele, e todos os números maiores que ele. Números grandes são colocados atrás dele. Esse processo é chamado de classificação rápida. O algoritmo para classificação rápida é:
1) Defina duas variáveis I e J. Ao iniciar a classificação, I:=1, J:=N;
2) Use o primeiro elemento do array como dado chave e atribua-o a X, ou seja, X:=A[1];
3) Pesquise para frente a partir de J, ou seja, pesquise para frente a partir de trás (J:=J-1), encontre o primeiro valor menor que X e troque os dois;
4) Pesquise para trás a partir de I, ou seja, pesquise de frente para trás (I:=I+1), encontre o primeiro valor maior que X e troque os dois;
5) Repita os passos 3 e 4 até I=J;
Por exemplo: os valores do array A a serem classificados são: (dados-chave iniciais X:=49)
A[1] A[2] A[3] A[4] A[5] A[6] A[7]:
49 38 65 97 76 13 27
Após a primeira troca: 27 38 65 97 76 13 49
(Depois de pesquisar por trás de acordo com a terceira etapa do algoritmo para a segunda troca: 27 38 49 97 76 13 65
(Siga a quarta etapa do algoritmo e comece pela frente para encontrar o valor>
Após a terceira troca: 27 38 13 97 76 49 65
(De acordo com a quinta etapa do algoritmo, a terceira etapa do algoritmo será executada novamente a partir do final para encontrar a quarta troca: 27 38 13 49 76 97 65
(Siga o quarto passo do algoritmo e comece pela frente para encontrar um valor maior que X, 97>49, troque os dois, neste momento J:=4)
Neste momento, ao executar o terceiro passo, verifica-se que I=J, finalizando assim a ordenação rápida. O resultado após a ordenação rápida é: 27 38 13 49 76 97 65, ou seja, todos os números maiores que 49 estão em 49. , então os números menores que 49 estão todos na frente de 49.
A classificação rápida consiste em chamar esse processo recursivamente - dividir a sequência de dados com 49 como ponto médio, realizar uma classificação rápida semelhante na parte frontal e traseira, respectivamente, completando assim a classificação rápida de toda a sequência de dados e, finalmente, transformar a sequência de dados em uma sequência ordenada An De acordo com esta ideia, todo o processo de classificação rápida da matriz A acima é mostrado na Figura 6:
Estado inicial {49 38 65 97 76 13 27}
Após uma classificação rápida, ele é dividido em {27 38 13} 49 {76 97 65}
Classifique rapidamente as partes frontal e traseira, respectivamente {13} 27 {38}
fim fim {49 65} 76 {97} 49 {65} fim fim
************************************************** ****************************
Figura 6 Descrição do algoritmo de classificação rápida ao longo do processo de classificação rápida
1) Suponha que N (assumindo N = 10) números sejam armazenados na matriz S;
2), em S[1. . Tome qualquer elemento em N] como base de comparação, por exemplo, tome T=S[1]. O objetivo inicial é determinar a posição K onde T deve estar no resultado da classificação. . . K-1]<=S[K]<=S[K+1..N], ou seja, os números antes de S[K] são todos menores que S[K], e os números depois de S[K] são todos maiores que S[ K];
3) Usar a ideia de dividir para conquistar (ou seja, a estratégia de transformar o grande e o pequeno em pequeno) pode melhorar ainda mais S[1. . K-1] e S[K+1. . N] Os dois conjuntos de dados são então classificados rapidamente até que haja apenas um dado no objeto de agrupamento.
Se os dados específicos forem os seguintes, o primeiro processo de classificação rápida é:
Subscrito da matriz: 1 2 3 4 5 6 7 8 9 10
45 36 18 53 72 30 48 93 15 36
eu
(1) 36 36 18 53 72 30 48 93 15 45
(2) 36 36 18 45 72 30 48 93 15 53
(3) 36 36 18 15 72 30 48 93 45 53
(4) 36 36 18 15 45 30 48 93 72 53
(5) 36 36 18 15 30 45 48 93 72 53