Fui exposto a vários princípios básicos do algoritmo desde que aprendi a estrutura de dados, mas nunca a pratiquei desde que terminei o exame. Quando eu estava desenvolvendo, também verifiquei quando o usei. Agora estou aprendendo JavaScript. Vou levar esse tempo para organizar vários algoritmos básicos e escrever código na sintaxe JS e PHP, respectivamente.
1. Classificação de bolhas
Princípio: Compare os números adjacentes em pares e troque -os em ordem pequena a grande ou grande a pequena. Após uma viagem, o maior ou o menor número é trocado até o último dígito e, em seguida, compare -os e troque desde o início até o segundo até o último dígito termine.
Complexidade do tempo: Caso médio: o (n2) Melhor caso: o (n) Pior caso: o (n2)
Complexidade espacial: o (1)
Estabilidade: estável
// javascript sintaxe var array = [23,0,32,45,56,75,43,0,34]; for (var i = 0; i <Array.Length; i ++) {var Issort = true; for (var j = 0; j <Array.Length - 1 - i; j ++) {if (array [j]> Array [j+1]) {Issort = false; var temp = matriz [j]; array [j] = array [j + 1]; matriz [j + 1] = temp; }} if (iSSort) {break; }} console.log (Array); <? php $ array = [23,0,32,45,56,75,43,0,34]; para ($ i = 0; $ i <count ($ Array); $ i ++) {$ Issort = true; para ($ j = 0; $ j <count ($ array) - 1; $ j ++) {if ($ Array [$ j]> $ Array [$ j+1]) {$ ISSORT = false; $ temp = $ array [$ j]; $ array [$ j] = $ array [$ j + 1]; $ array [$ j + 1] = $ temp; }} if ($ ISSort) {break; }} var_dump ($ array);?>2. Classificação simples de seleção
Princípio: Ao comparar as palavras-chave NI, selecione o registro com a menor palavra-chave dos registros n-i+1 e troque-o com i (1 <= i <= n) th registros. O desempenho da classificação simples de seleção é um pouco melhor que a classificação de bolhas.
Complexidade do tempo: Caso médio: o (n2) Melhor caso: o (n) Pior caso: o (n2)
Complexidade espacial: o (1)
Estabilidade: instável
// javascript var Array = [23,0,32,45,56,75,43,0,34]; for (var i = 0; i <Array.Length - 1; i ++) {var pos = i; for (var j = i+1; j <array.length; j ++) {if (array [j] <array [pos]) {pos = j; }} var temp = array [i]; array [i] = array [POS]; Array [POS] = temp; } console.log (Array); <? php $ array = [23,0,32,45,56,75,43,0,34]; para ($ i = 0; $ i <count ($ Array); $ i ++) {$ pos = $ i; para ($ j = $ i+1; $ j <count ($ array); $ j ++) {if ($ array [$ j] <$ Array [$ pos]) {$ pos = $ j; }} $ temp = $ array [$ i]; $ array [$ i] = $ array [$ pos]; $ array [$ pos] = $ temp; } var_dump ($ array);?>3. Insira diretamente o tipo
Princípio: Insira um registro na tabela ordenada classificada, obtendo assim uma nova tabela ordenada com 1 incrementos de registros. Ou seja, primeiro trate o primeiro registro da sequência como uma subsequência ordenada e, em seguida, insira -o a um do segundo registro até que toda a sequência seja ordenada. Melhor desempenho do que método de bolha e classificação de seleção
Complexidade do tempo: Caso médio: o (n2) Melhor caso: o (n) Pior caso: o (n2)
Complexidade espacial: o (1)
Estabilidade: estável
// javascript var Array = [23,0,32,45,56,75,43,0,34]; for (var j = 0; j <array.length; j ++) {var key = array [j]; var i = j - 1; while (i> -1 && Array [i]> key) {Array [i + 1] = Array [i]; i = i - 1; } matriz [i + 1] = key; } console.log (Array); <? php // inserir diretamente classificar $ array = [23,0,32,45,56,75,43,0,34]; para ($ i = 0; $ i <count ($ Array); $ i ++) {$ key = $ Array [$ i]; $ j = $ i - 1; while ($ J> -1 && $ Array [$ j]> $ key) {$ Array [$ j +1] = $ array [$ j]; $ j = $ j - 1; } $ array [$ j + 1] = $ key; } var_dump ($ array);?>4. Classificação rápida
Princípio: Através de uma classificação, os dados a serem classificados são divididos em duas partes independentes, e todos os dados em parte são menores que todos os dados da outra parte e, em seguida, as duas partes dos dados são rapidamente classificadas de acordo com esse método. Todo o processo de classificação pode ser executado recursivamente para alcançar todos os dados se tornando uma sequência ordenada.
Complexidade do tempo: Caso médio: o (nlog2n) Melhor caso: o (nlog2n) Pior caso: o (n2)
Complexidade espacial: o (nlog2n)
Estabilidade: instável
// JavaScript Quick Classing var Array = [23,0,32,45,56,75,43,0,34]; var wicksort = function (arr) {if (arr.length <= 1) {return arr; } // Verifique o número de elementos na matriz, se for menor ou igual a 1, será retornado. var pivotIndex = math.floor (arr.length/2); // var pivot = arr.splice (pivotindex, 1) [0]; // selecione "benchmark" (pivô) e separá -lo da matriz original, VAR esquerda = []; for (var i = 0; i <arn.length; i ++) // transweep a matriz, coloque elementos menores que o "benchmark" no subconjunto à esquerda e elementos maiores que o benchmark no subconjunto à direita. {if (arr [i] <pivot) {left.push (arr [i]); } else {right.push (arr [i]); }} Retorne o QuickSort (esquerda) .Concat ([Pivot], QuickSort (à direita); // Repita esse processo continuamente para obter a matriz classificada. }; var newArray = Quicksort (Array); console.log (newArray); <? php $ array = [23,0,32,45,56,75,43,0,34]; função Quick_sort ($ arr) {// Primeiro determine se você precisa continuar $ length = count ($ arr); if ($ length <= 1) {return $ arr; } $ base_num = $ arr [0]; // Selecione uma régua para selecionar o primeiro elemento // Inicialize duas matrizes $ esquerd_array = Array (); // $ right_array menos que o governante = Array (); // para ($ i = 1; $ i <$ i); $ arr [$ i]) {// coloque na matriz esquerda $ esquerda_array [] = $ arr [$ i]; } else {// coloque na direita $ right_array [] = $ arr [$ i]; }} // o mesmo método de classificação para as matrizes esquerda e direita, respectivamente, // chamando esta função de forma recursiva e gravando o resultado $ esquerd_array = quick_sort ($ left_array); $ right_array = quick_sort ($ right_array); // Mesclar o régua esquerdo para a direita Return Array_Merge ($ esquerd_array, Array ($ base_num), $ right_array); } $ newArray = Quick_sort ($ Array); var_dump ($ newArray);?>5
Princípio: Primeiro, divida toda a sequência de registros a ser classificada em várias sub-seqüências para inserção e classificação diretas. Quando os registros em toda a sequência são "basicamente ordenados", insira e classifique os registros inteiros em sequência. .
Complexidade do tempo: Caso médio: o (n√n) Melhor caso: o (nlog2n) Pior caso: o (n2)
Complexidade espacial: o (1)
Estabilidade: instável
// Javascript Hill Sort Array = [23,0,32,45,56,75,43,0,34]; var shellSort = function (arr) {var comprimento = arr.length; var h = 1; while (h <comprimento/3) {h = 3*h+1; // define intervalo} while (h> = 1) {for (var i = h; i <comprimento; i ++) {for (var j = i; j> = h && arr [j] <arr [jh]; j-= h) {var te temp = arr [jh]; arr [jh] = arr [j]; arr [j] = temp; }} h = (h-1)/3; } retornar arr; } var newArray = ShellSort (Array); console.log (newArray); <? php // colina classy $ matriz = [23,0,32,45,56,75,43,0,34]; function shellsort ($ arr) {$ length = count ($ arr); $ h = 1; while ($ h <$ comprimento/3) {$ h = 3*$ h+1; // Defina intervalo} while ($ h> = 1) {para ($ i = $ h; $ i <$ length; $ i ++) {para ($ j = $ i; $ j> = $ H && $ [$ j] <$ priv [$ $ arr [$ j- $ h] = $ arr [$ j]; $ arr [$ j] = $ temp; }} $ h = ($ h-1)/3; } retornar $ arr; } $ newArray = ShellSort ($ Array); var_dump ($ newArray)?>6. Pedido
Princípio: Supondo que a sequência inicial contenha N registros, ela pode ser considerada como N ordenada subseqüência, cada subsequência tem um comprimento de 1 e depois se fundida em pares para obter (o menor número inteiro não inferior a N/2) ordenado subseqüência com comprimentos de 2 ou 1 e fusão em pares ... repetir dessa maneira até que uma sequência e uma sequência com N é a sequência n.
Complexidade do tempo: Caso médio: o (nlog2n) Melhor caso: o (nlog2n) Pior caso: o (nlog2n)
Complexidade espacial: o (1)
Estabilidade: estável
// JavaScript Merge Classing Função isarray1 (arr) {if (object.prototype.tostring.call (arr) == '[objeto array]') {return true; } else {return false; }} função mescle (esquerda, direita) {var resultado = []; if (! isarray1 (esquerda)) {esquerda = [esquerda]; } if (! isarray1 (à direita)) {direita = [direita]; } while (left.length> 0 && Right.Length> 0) {if (esquerda [0] <direita [0]) {result.push (esquerd.shift ()); } else {resultado.push (right.shift ()); }} retornar resultado.CONCAT (esquerda) .CONCAT (direita); } função mesck (arr) {var len = arr.length; var lim, trabalho = []; var i, j, k; if (len == 1) {return arr; } para (i = 0; i <len; i ++) {work.push (arr [i]); } work.push ([]); for (lim = len; lim> 1;) {// lim é o comprimento do agrupamento para (j = 0, k = 0; k <lim; j ++, k = k+2) {trabalho [j] = mescla (trabalho [k], trabalho [k+1]); } trabalho [j] = []; lim = math.floor ((lim+1)/2); } retornar trabalho [0]; } var array = [23,0,32,45,56,75,43,0,34]; console.log (Mergesort (Array)); <? php // função de classificação de entendimento mesclado (& $ arr) {$ len = count ($ arr); // encontrando o comprimento da matriz msort ($ arr, 0, $ len-1); } // O programa que realmente implementa a função de classificação da mesclagem msort (& $ arr, $ esquerda, $ direita) {if ($ esquerda <$ direita) {// indica que há 1 elemento extra na subsequência, então é necessário dividir, classificar separadamente, mesclar // calcular a posição de split /2 /2 vá para o $ Center = Floor (($ LEFRETE) // Chamada recursiva classifica o lado esquerdo novamente: msort ($ arr, $ esquerda, $ Center); // Ligue recursivamente para classificar o lado direito novamente MSORT ($ ARN, $ Center+1, $ Right); // Mesclar os resultados de classificação MergeArray ($ arr, $ esquerda, $ Center, $ direito); }} // Combine dois números ordenados em uma função de matriz ordenada MergeArray (& $ arr, $ esquerda, $ Center, $ direita) {// Defina duas marcas de posição inicial $ a_i = $ deixado; $ b_i = $ Center+1; while ($ a_i <= $ Center && $ B_I <= $ Right) {// quando nem a matriz A nem a matriz B atravessa o limite if ($ arr [$ a_i] <$ arr [$ b_i]) {$ temp [] = $ arr [$ a_i ++]; } else {$ temp [] = $ arr [$ b_i ++]; }} // julgue se todos os elementos da matriz A são usados. Caso contrário, insira todos os elementos na matriz c: while ($ a_i <= $ Center) {$ temp [] = $ arr [$ a_i ++]; } // julgue se todos os elementos da matriz B são usados. Caso contrário, insira todos os elementos na matriz c: while ($ b_i <= $ correto) {$ temp [] = $ arr [$ b_i ++]; } // Escreva a peça classificada em $ arc em $ arr: para ($ i = 0, $ len = count ($ temp); $ i <$ len; $ i ++) {$ arr [$ esquerda+$ i] = $ temp [$ i]; }} $ arr = Array (23,0,32,45,56,75,43,0,34); Mergesort ($ ARR); var_dump ($ arr);?>7. Classificação de heap
Princípio: a classificação de heap é um método de classificação usando o heap. A idéia básica é: construir a sequência a ser classificada em uma grande pilha superior. Neste momento, o valor máximo de toda a sequência é o nó raiz da parte superior da pilha. Remova-o (de fato, é trocar com o elemento final da matriz de heap, e o elemento final é o valor máximo) e, em seguida, reconstruir as seqüências N-1 restantes em uma pilha, para que o valor da submazimum dos elementos N seja obtido. Isso resultará em uma execução repetida e uma sequência ordenada poderá ser obtida.
Complexidade do tempo: Caso médio: o (nlog2n) Melhor caso: o (nlog2n) Pior caso: o (nlog2n)
Complexidade espacial: o (1)
Estabilidade: instável
// JavaScript Heap Sort Array var = [23,0,32,45,56,75,43,0,34]; function heapsort (array) {for (var i = math.floor (array.length / 2); i> = 0; i-) {heapadjust (matriz, i, array.length-1); // Construir matriz de matriz em um grande heap superior} para (i = array.length-1; i> = 0; i-) {/*trocar o nó raiz*/var temp = matriz [i]; array [i] = array [0]; matriz [0] = temp; /*A matriz restante continua sendo incorporada em um grande heapjust (matriz, 0, i - 1); } retornar a matriz; } função heapadjust (array, start, max) {var temp = array [start]; // temp é o valor do nó raiz para (var j = 2 * start; j <max; j * = 2) {if (j <max && Array [j] <array [j+1]) {// obtenha o subsistro de substrit } if (temp> = array [j]) quebra; matriz [start] = matriz [j]; start = j; } matriz [start] = temp; } var newArray = heapsort (matriz); console.log (newArray); <? php // função de classificação heap heapsort (& $ arr) {#initheap ($ arr, 0, count ($ arr) - 1); #Start Trocar os nós da cabeça e da cauda e reduzir um nó de extremidade por vez e ajustar a pilha até que haja um elemento restante para ($ end = count ($ arr)-1; $ end> 0; $ end--) {$ temp = $ arr [0]; $ arr [0] = $ arr [$ end]; $ arr [$ end] = $ temp; AJUSTNODES ($ ARR, 0, $ END - 1); }} #Initialize a pilha máxima, inicie no último nó não folhas e o último nó não folhas é numerado como comprimento da matriz/2 função redondo initeap (& $ arr) {$ len = contagem ($ arr); para ($ start = piso ($ len / 2) - 1; $ start> = 0; $ start--) {ajustnodes ($ arr, $ start, $ len - 1); }}#AjustNodes#@param $ ARN ARRAY A ser ajustado#@param $ Inicie as coordenadas do nó pai a ser ajustado#@param $ ter as coordenadas do nó final para ser ajustado função AJUSTNODES (& $ ARN, $ START, $ END) {$ maxinx = $ start; $ len = $ end + 1; #O comprimento da peça a ser ajustado $ leftChildinx = ($ START + 1) * 2 - 1; #Left Child Coordenine $ RETERCHILDINX = ($ START + 1) * 2; #Right Child Coordenine #Se a peça a ser ajustada tiver um filho esquerdo se ($ leftchildinx + 1 <= $ len) {#get a coordenada mínima do nó if ($ arr [$ maxinx] <$ arr [$ leftChildinx]) {$ maxinx = $ leftChildinx; } #Se a peça a ser ajustada possui um nó infantil certo se ($ rightChildinx + 1 <= $ len) {if ($ arr [$ maxinx] <$ arr [$ rightchildinx]) {$ maxinx = $ rightChildinx; }}} #Swap nó pai e nó máximo if ($ start! = $ Maxinx) {$ temp = $ arr [$ start]; $ arr [$ start] = $ arr [$ maxinx]; $ arr [$ maxinx] = $ temp; #Se o nó infantil após a troca possui nós filhos, continue ajustando se (($ maxinx + 1) * 2 <= $ len) {AJustnodes ($ arr, $ maxinx, $ end); }}} $ arr = Array (23,0,32,45,56,75,43,0,34); heapsort ($ arr); var_dump ($ arr);?>8. Classificação da cardinalidade
Princípio: corte os números inteiros em números diferentes por dígitos e compare -os separadamente por cada dígito. Como os números inteiros também podem expressar strings (como nomes ou datas) e números de ponto flutuante em formatos específicos, a classificação do radix não é usada apenas para inteiros.
Complexidade do tempo: Caso médio: O (D (R+N)) Melhor caso: O (D (N+RD)) Pior caso: O (D (R+N)) R: Cardinalidade das palavras -chave D: Comprimento n: Número de palavras -chave
Complexidade espacial: O (RD+N)
Estabilidade: estável
<? php #Blassorting, aqui apenas números inteiros positivos são classificados. Quanto aos números negativos e números de ponto flutuante, é necessário complemento. Você está interessado em estudar #Classificação #@param $ ARN ARRAY A ser classificado #@param $ digit_num classificar de acordo com o número de dígitos function Counting_sort (& $ arr, $ digit_num = false) {if ($ digit_num! == false) {#if o parâmetro count ($ arr); }} else {$ arr_temp = $ arr; } $ max = max ($ arr); $ time_arr = array (); #Storage matriz de elementos Ocorrências#Inicialize a matriz de ocorrências para ($ i = 0; $ i <= $ max; $ i ++) {$ time_arr [$ i] = 0; } #Statize as ocorrências de cada elemento para ($ i = 0; $ i <count ($ arr_temp); $ i ++) {$ time_arr [$ arr_temp); $ i ++) {$ time_arr [$ arr_temp [$ i]] ++; } #Statify as ocorrências de cada elemento que é menor ou igual a ele para ($ i = 0; $ i <count ($ time_arr) - 1; $ i ++) {$ time_arr [$ i +1] += $ time_arr [$ i]; } #Sort a matriz usando o número de ocorrências para ($ i = count ($ arr) - 1; $ i> = 0; $ i--) {$ stored_arr [$ time_arr [$ ar_temp [$ i]] - 1] = $ arr [$ i]; $ time_arr [$ arr_temp [$ i]]-; } $ arr = $ STORD_ARR; ksort ($ arr); #Ignore a perda de eficiência da classificação de chaves desta vez} #Calculate o número de bits de uma determinada função de número get_digit ($ número) {$ i = 1; while ($ número> = pow (10, $ i)) {$ i ++; } retornar $ i; } #get o número de dígitos de um número da função de dígitos únicos get_specific_digit ($ num, $ i) {if ($ num <pow (10, $ i - 1)) {return 0; } Retornar piso ($ num % pow (10, $ i) / POW (10, $ i - 1)); } #Black Strating, contendo a classificação como uma função de processo de sub-classificação Radix_sort (& $ arr) {#first Encontre o maior dígito na matriz $ max = max ($ arr); $ max_digit = get_digit ($ max); para ($ i = 1; $ i <= $ max_digit; $ i ++) {conting_sort ($ arr, $ i); }} $ arr = Array (23,0,32,45,56,75,43,0,34); radix_sort ($ arr); var_dump ($ arr);?>O exposto acima é todo o conteúdo deste artigo. Espero que seja útil para o aprendizado de todos e espero que todos apoiem mais o wulin.com.