Entrevistas escritas geralmente envolvem vários algoritmos. Este artigo apresenta brevemente alguns algoritmos comumente usados e os implementa em JavaScript.
1. Insira a classificação
1) Introdução ao algoritmo
A descrição do algoritmo do inserção-Sort é um algoritmo de classificação simples e intuitivo. Ele funciona construindo uma sequência ordenada, para dados não classificados, digitaliza para trás e para frente na sequência classificada, encontre a posição correspondente e insira -os. Na implementação da classificação de inserção, geralmente é usada a classificação no local (ou seja, o espaço extra de O (1) é necessário); portanto, durante o processo de varredura de trás para frente, os elementos classificados precisam ser movidos repetidamente para trás para fornecer espaço de inserção para os elementos mais recentes.
2) Descrição do algoritmo e implementação
De um modo geral, a classificação de inserção é implementada em uma matriz usando no local. O algoritmo específico é descrito da seguinte forma:
A partir do primeiro elemento, o elemento pode ser considerado classificado;
Retire o próximo elemento e digitalize para trás e para frente na sequência já classificada de elementos;
Se o elemento (classificado) for maior que o novo elemento, mova o elemento para a próxima posição;
Repita a etapa 3 até que o elemento classificado seja encontrado onde o novo elemento é menor ou igual;
Depois de inserir um novo elemento nessa posição;
Repita as etapas 2 a 5.
Implementação de código JavaScript:
função inserttionsort (array) {if (object.prototype.toString.call (array) .slice (8, -1) === 'Array') {for (var i = 1; i <array.length; i ++) {var chave = matriz [i]; var j = i - 1; while (j> = 0 && Array [j]> key) {Array [j + 1] = Array [j]; J--; } matriz [j + 1] = key; } retornar a matriz; } else {return 'Array não é uma matriz!'; }}3) Análise de algoritmo
Melhor caso: as matrizes de entrada são classificadas em ordem crescente. T (n) = O (n)
No pior caso: a matriz de entrada é classificada em ordem decrescente. T (n) = O (n2)
Média: t (n) = O (n2)
Dois, tipo de inserção binária
1) Introdução ao algoritmo
A classificação binária-insert-sort é um algoritmo de classificação que faz pequenas alterações no algoritmo de classificação de inserção direta. A maior diferença entre ele e o algoritmo de classificação de inserção direta é que, ao procurar posições de inserção, o método de pesquisa binária é usado, que tem uma certa melhoria na velocidade.
2) Descrição do algoritmo e implementação
De um modo geral, a classificação de inserção é implementada em uma matriz usando no local. O algoritmo específico é descrito da seguinte forma:
A partir do primeiro elemento, o elemento pode ser considerado classificado;
Retire o próximo elemento e encontre a posição do primeiro número maior do que na sequência já classificada de elementos;
Depois de inserir um novo elemento nessa posição;
Repita as duas etapas acima.
Implementação de código JavaScript:
function binaryinsertionsort (matriz) {if (object.prototype.toString.call (array) .slice (8, -1) === 'Array') {for (var i = 1; i <array.length; i ++) {var key = array [i], esquerda = 0, direito = i - 1; while (esquerda <= direita) {var middle = parseInt ((esquerda + direita) / 2); if (chave <array [meio]) {direita = meio - 1; } else {esquerda = meio + 1; }} para (var j = i-1; j> = esquerda; j--) {array [j + 1] = array [j]; } matriz [esquerda] = key; } retornar a matriz; } else {return 'Array não é uma matriz!'; }}3) Análise de algoritmo
Melhor caso: t (n) = O (nLogn)
Pior caso: t (n) = O (n2)
Média: t (n) = O (n2)
3. Selecione a classificação
1) Introdução ao algoritmo
Seleção-Sort é um algoritmo de classificação simples e intuitivo. Como funciona: primeiro encontre o menor elemento (grande) na sequência não classificada, armazene -o na posição inicial da sequência classificada e continue procurando o menor elemento (grande) dos elementos restantes e coloque -o no final da sequência classificada. E assim por diante até que todos os elementos sejam classificados.
2) Descrição do algoritmo e implementação
A seleção direta dos registros N pode ser obtida através de passes N-1 para selecionar e classificar diretamente. O algoritmo específico é descrito da seguinte forma:
Estado inicial: a área não ordenada é r [1..n], e a área ordenada está vazia;
Quando a I-Th Ordering (i = 1,2,3 ... n-1) começa, as áreas atuais ordenadas e não ordenadas são r [1..i-1] e r (i..n), respectivamente. Este pedido seleciona o registro r [k] com a menor palavra -chave da área não ordenada atual e a troca com o primeiro registro r da área não ordenada, de modo que r [1..i] e r [i+1..n) se tornem uma nova área ordenada com um aumento no número de registros e uma nova área não ordenada com uma diminuição no número de registros;
A viagem N-1 termina e a matriz é ordenada.
Implementação de código JavaScript:
Função SeleçãoRort (Array) {if (object.prototype.tostring.call (array) .slice (8, -1) === 'Array') {var len = Array.length, temp; for (var i = 0; i <len - 1; i ++) {var min = array [i]; for (var j = i+1; j <len; j ++) {if (array [j] <min) {temp = min; min = matriz [j]; matriz [j] = temp; }} array [i] = min; } retornar a matriz; } else {return 'Array não é uma matriz!'; }}3) Análise de algoritmo
Melhor caso: t (n) = O (n2)
Pior caso: t (n) = O (n2)
Média: t (n) = O (n2)
4. Classificação de bolhas
1) Introdução ao algoritmo
A classificação de bolhas é um algoritmo de classificação simples. Ele visita repetidamente as seqüências a serem classificadas, compara dois elementos por vez e os troca se estiverem incorretos. O trabalho de visitar a sequência é repetido até que nenhuma troca seja necessária, ou seja, a sequência foi classificada. A origem desse algoritmo é porque quanto menor o elemento "flutua" lentamente para o topo da sequência via troca.
2) Descrição do algoritmo e implementação
O algoritmo específico é descrito da seguinte forma:
Compare elementos adjacentes. Se o primeiro for maior que o segundo, troque dois deles;
Faça o mesmo trabalho para cada par de elementos adjacentes, desde o início do primeiro par até o final do último par, para que o último elemento seja o maior número;
Repita as etapas acima para todos os elementos, exceto o último;
Repita as etapas 1 a 3 até que a classificação esteja concluída.
Implementação de código JavaScript:
função bubblesort (array) {if (object.prototype.toString.call (array) .slice (8, -1) === 'Array') {var len = array.length, temp; for (var i = 0; i <len - 1; i ++) {for (var j = len - 1; j> = i; j--) {if (array [j] <array [j - 1]) {temp = array [j]; array [j] = array [j - 1]; matriz [j - 1] = temp; }}} retornar a matriz; } else {return 'Array não é uma matriz!'; }}3) Análise de algoritmo
Melhor caso: t (n) = O (n)
Pior caso: t (n) = O (n2)
Média: t (n) = O (n2)
5. Classificação rápida
1) Introdução ao algoritmo
A idéia básica da classificação rápida: divida os registros a serem classificados em duas partes independentes por meio de uma ordem, e as palavras -chave de alguns registros são menores que as da outra parte. Em seguida, os dois registros podem continuá -los separadamente para alcançar a ordem de toda a sequência.
2) Descrição do algoritmo e implementação
A classificação rápida usa o método de divisão para dividir uma string em duas sub-listas. O algoritmo específico é descrito da seguinte forma:
Escolher um elemento da sequência é chamado de "princípio" (pivô);
Reordenar a sequência, todos os elementos com menor que o valor de referência são colocados na frente da referência e todos os elementos com maior que o valor de referência são colocados atrás da referência (o mesmo número pode ser colocado em ambos os lados). Após a saída desta partição, a referência está no meio da sequência. Isso é chamado de operação de partição;
Classifique recursivamente as sub-seqüências menores que o elemento de referência e as sub-seqüências maiores que o elemento de referência.
Implementação de código JavaScript:
// Método Uma função QuickSort (Array, esquerda, direita) {if (object.prototype.toString.Call (Array) .Slice (8, -1) === 'Array' && typeof esquerd === 'Número' && Typeof Right === 'Número') {se esquerda <direita) {var x = [] for (var j = esquerda; j <= direita; j ++) {if (array [j] <= x) {i ++; temp = matriz [i]; Array [i] = Array [J]; matriz [j] = temp; }} QuickSort (Array, à esquerda, i - 1); Quicksort (Array, I + 1, à direita); }; } else {return Array não é uma matriz ou esquerda ou direita não é um número! '; }} var aaa = [3, 5, 2, 9, 1]; Quicksort (AAA, 0, aaa.length - 1); console.log (AAA); // Método 2 var wicksort = function (arr) {if (arr.length <= 1) {return arr; } var pivotIndex = math.floor (ar.Length / 2); var pivot = arr.splice (pivotIndex, 1) [0]; var esquerdo = []; var à direita = []; for (var i = 0; i <arr.length; i ++) {if (arr [i] <pivot) {left.push (arr [i]); } else {right.push (arr [i]); }} Retorne QuickSort (esquerda) .Concat ([Pivot], QuickSort (direita)); };3) Análise de algoritmo
Melhor caso: t (n) = O (nLogn)
Pior caso: t (n) = O (n2)
Média: t (n) = O (nLogn)
6. Classificação de heap
1) Introdução ao algoritmo
A classificação de heap refere -se a um algoritmo de classificação projetado usando a estrutura de dados da heap. O empilhamento é uma estrutura que é aproximadamente completamente binária e satisfaz as propriedades do empilhamento: ou seja, o valor da chave ou o índice de um nó filho é sempre menor que (ou maior que) seu nó pai.
2) Descrição do algoritmo e implementação
O algoritmo específico é descrito da seguinte forma:
A sequência inicial de palavras -chave a ser classificada (R1, R2 ... RN) é construída em uma grande pilha superior, que é a área inicial não ordenada;
Trocar o elemento superior r [1] com o último elemento r [n] e, neste momento, uma nova região não ordenada (R1, R2, ... RN-1) e uma nova região ordenada (RN) são obtidas e R [1,2 ... n-1] <= r [n] é satisfeito;
Como o novo Heap Top R [1] após a troca pode violar as propriedades da pilha, é necessário ajustar a área não ordenada atual (R1, R2, ... RN-1) ao novo heap e depois trocar r [1] com o último elemento da área não ordenada para obter uma nova área não encomendada (R1, R2 ... RN-2) e uma ordem não ordenada. Repita esse processo até que o número de elementos na área ordenada seja N-1 e todo o processo de classificação seja concluído.
Implementação de código JavaScript:
/*MÉTODO DESCRIÇÃO: Classificação de heap @param Array Array a ser classificado*/function heapsort (Array) {if (object.prototype.toString.Call (Array) .slice (8, -1) === 'Array') {// Construa o heap var heapsize = array.Lain. for (var i = math.floor (heapsize / 2); i> = 0; i--) {heapify (matriz, i, heapsize); } // Classificação de heap para (var j = heapsize-1; j> = 1; j--) {temp = array [0]; Array [0] = Array [J]; matriz [j] = temp; heapify (matriz, 0, - -heapsize); }} else {return Array não é uma matriz! '; }}/ * Método Descrição: Mantenha as propriedades do heap @param prta Array @param x Array Subscrito @param len size */function heapify (arr, x, len) {if (object.prototype.toString.call (arr) .slice (8, -1) === `` `` `` ``) '{if (object.Prototype' & styTyTing.Call (arr) .slice (8 '') == ”` `` `` `` ``) '{if (object.prototype' & stystring.call (arr) .lice (8 '-1) ”) 1, mais grande = x, temp; if (Len && arr [l]> arr [maior]) {maior = l; } if (r <len && arr [r]> arr [maior]) {maior = r; } if (maior! = x) {temp = arr [x]; arr [x] = arr [maior]; arr [maior] = temp; heapify (arr, grande, len); }} else {return 'arr é uma matriz ou x não é um número!'; }}3) Análise de algoritmo
Melhor caso: t (n) = O (nLogn)
Pior caso: t (n) = O (nLogn)
Média: t (n) = O (nLogn)
7. ordenando
1) Introdução ao algoritmo
A classificação de mesclagem é um algoritmo de classificação eficaz com base na operação de mesclagem. Esse algoritmo é uma aplicação muito típica de dividir e conquistar. A classificação de mesclagem é um método de classificação estável. Mesclar as subsequências ordenadas para obter uma sequência completamente ordenada; isto é, faça cada primeira ordem subsequente e, em seguida, faça a ordem dos segmentos subseqüentes. Se duas tabelas ordenadas forem mescladas em uma tabela ordenada, ela é chamada de fusão de duas vias.
2) Descrição do algoritmo e implementação
O algoritmo específico é descrito da seguinte forma:
Divida a sequência de entrada do comprimento n em duas subsequências de comprimento N/2;
Essas duas subsequências são classificadas juntas separadamente;
Mesclar as duas subsequências classificadas em uma sequência final classificada.
Implementação de código JavaScript:
Função Mescret (Array, P, R) {if (p <r) {var q = Math.floor ((P + R) / 2); mesclar (Array, P, Q); mesclar (matriz, q + 1, r); mesclar (Array, P, Q, R); }} função mescle (array, p, q, r) {var n1 = q - p + 1, n2 = r - q, esquerda = [], direita = [], m = n = 0; for (var i = 0; i <n1; i ++) {esquerda [i] = array [p+i]; } for (var j = 0; j <n2; j ++) {direita [j] = array [q + 1 + j]; } esquerda [n1] = direita [n2] = número.max_value; for (var k = p; k <= r; k ++) {if (esquerda [m] <= direita [n]) {array [k] = esquerda [m]; m ++; } else {array [k] = direita [n]; n ++; }}}3) Análise de algoritmo
Melhor caso: t (n) = O (n)
Pior caso: t (n) = O (nLogn)
Média: t (n) = O (nLogn)
8. Classificação do balde
1) Introdução ao algoritmo
O princípio da classificação do balde: supondo que os dados de entrada sejam distribuídos uniformemente, os dados são divididos em um número limitado de baldes e cada balde é classificado separadamente (é possível usar outros algoritmos de classificação ou continuar a usar a classificação do balde de maneira recursiva).
2) Descrição do algoritmo e implementação
O algoritmo específico é descrito da seguinte forma:
Defina uma matriz quantitativa como um balde vazio;
Itera através dos dados de entrada e coloque os dados no balde correspondente um por um;
Classifique cada balde que não está vazio;
Coloque os dados classificados de um balde vazio.
Implementação de código JavaScript:
/*MÉTODO DESCRIÇÃO: CLASTE CLASTE @PARAM Array Array @param Número de buckets*/ function bucketsort (array, num) {if (array.length <= 1) {return Array; } var len = array.length, buckets = [], resultado = [], min = max = matriz [0], regex = '/^[1-9]+[0-9]*$/', espaço, n = 0; num = num || ((num> 1 && regex.test (num))? num: 10); for (var i = 1; i <len; i ++) {min = min <= array [i]? Min: Array [i]; max = max> = array [i]? Max: Array [i]; } espaço = (max - min + 1) / num; for (var j = 0; j <len; j ++) {var index = math.floor ((Array [j] - min) / espaço); if (baldes [index]) {// bucket não vazio, insira classificação var k = buckets [index] .Length - 1; while (k> = 0 && buckets [index] [k]> Array [j]) {buckets [index] [k + 1] = baldes [index] [k]; k--; } baldes [index] [k + 1] = array [j]; } else {// Bucket vazio, inicialize baldes [index] = []; baldes [índice] .push (matriz [j]); }} while (n <num) {resultado = resultado.concat (buckets [n]); n ++; } resultado de retorno; }3) Análise de algoritmo
Na melhor das hipóteses de classificação do balde, tempo linear O (n), a complexidade do tempo da classificação do balde depende da complexidade do tempo de classificar os dados entre os baldes, porque a complexidade do tempo de outras partes é O (n). Obviamente, quanto menor o balde for dividido, menos dados o balde é, menor tempo necessário para classificá -lo. Mas o consumo espacial correspondente aumentará.
9. Contagem de classificação
1) Introdução ao algoritmo
A Counting Sort é um algoritmo de classificação estável. A Count Strating usa uma matriz adicional C, onde o i-ésimo elemento é o número de elementos com um valor igual a I na matriz A a ser classificada. Então, de acordo com a matriz C, os elementos em A são organizados para a posição correta. Só pode classificar números inteiros.
2) Descrição do algoritmo e implementação
O algoritmo específico é descrito da seguinte forma:
Encontre os maiores e os menores elementos da matriz a ser classificada;
Conte o número de vezes cada elemento com um valor de i na matriz aparece e guarde-o no I-és I-és da matriz C;
Acumular todas as contagens (começando pelo primeiro elemento em C, cada item e o item anterior são adicionados);
Matriz de destino de preenchimento reverso: coloque cada elemento I no c (i) o item da nova matriz e subtraia C (i) por 1 para cada elemento.
Implementação de código JavaScript:
function contingSort (array) {var len = array.length, b = [], c = [], min = max = matriz [0]; for (var i = 0; i <len; i ++) {min = min <= array [i]? Min: Array [i]; max = max> = array [i]? Max: Array [i]; C [Array [i]] = C [Array [i]]? C [Array [i]] + 1: 1; } for (var j = min; j <max; j ++) {c [j + 1] = (c [j + 1] || 0) + (c [j] || 0); } for (var k = len - 1; k> = 0; k--) {b [c [array [k]] - 1] = array [k]; C [Array [K]]-; } retornar b; }3) Análise de algoritmo
Quando o elemento de entrada é n números inteiros entre 0 e K, seu tempo de execução é O (n + k). A classificação da contagem não é uma classificação de comparação, e a velocidade de classificação é mais rápida do que qualquer algoritmo de classificação de comparação. Como o comprimento da matriz C usado para contar depende da faixa de dados na matriz a ser classificada (igual à diferença entre os valores máximo e mínimo da matriz a ser classificada mais 1), isso faz com que a classificação da contagem requer muito tempo e memória para matrizes com uma grande faixa de dados.