He estado expuesto a varios conceptos básicos de algoritmos desde que aprendí la estructura de datos, pero nunca la he practicado desde que terminé el examen. Cuando me estaba desarrollando, también lo comprobé cuando lo usé. Ahora estoy aprendiendo JavaScript. Me tomaré este tiempo organizar varios algoritmos básicos y escribir código en la sintaxis JS y PHP, respectivamente.
1. Clasificación de burbujas
Principio: Compare los números adyacentes en parejas e intercambie en orden de pequeño a grande o grande a pequeño. Después de un viaje, el número más grande o más pequeño se intercambia hasta el último dígito, y luego compárelos e intercambie desde el principio hasta que termine el segundo dígito.
Complejidad del tiempo: Caso promedio: O (N2) Mejor caso: O (N) Peor Caso: O (N2)
Complejidad del espacio: O (1)
Estabilidad: establo
// JavaScript Syntax 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 = array [j]; matriz [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; for ($ 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. Clasificación de selección simple
Principio: Al comparar las palabras clave NI, seleccione el registro con la palabra clave más pequeña de los registros N-I+1 e intercambíla con los registros I (1 <= i <= n) th. El rendimiento de la clasificación de selección simple es ligeramente mejor que la clasificación de burbujas.
Complejidad del tiempo: Caso promedio: O (N2) Mejor caso: O (N) Peor Caso: O (N2)
Complejidad del espacio: O (1)
Estabilidad: inestable
// 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]; matriz [i] = array [pos]; matriz [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. Insertar directamente la clasificación
Principio: inserte un registro en la tabla ordenada ordenada, obteniendo así una nueva tabla ordenada con 1 incrementos de registros. Es decir, primero trate el primer registro de la secuencia como una posterior subsecuencia ordenada, y luego inserte uno por uno desde el segundo registro hasta que se ordene toda la secuencia. Mejor rendimiento que el método de burbujas y la clasificación de selección
Complejidad del tiempo: Caso promedio: O (N2) Mejor caso: O (N) Peor Caso: O (N2)
Complejidad del espacio: O (1)
Estabilidad: establo
// 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] = clave; } console.log (array); <? Php // Insertar directamente $ 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] = $ clave; } var_dump ($ array) ;?>4. Clasificación rápida
Principio: a través de una clasificación, los datos a ordenar se dividen en dos partes independientes, y todos los datos en parte son más pequeños que todos los datos en la otra parte, y luego las dos partes de los datos se clasifican rápidamente de acuerdo con este método. Todo el proceso de clasificación se puede realizar de manera recursiva para lograr que los datos completos se conviertan en una secuencia ordenada.
Complejidad del tiempo: Caso promedio: O (NLOG2N) Mejor caso: O (NLOG2N) Peor Caso: O (N2)
Complejidad del espacio: O (NLOG2N)
Estabilidad: inestable
// JavaScript Quick Sort Var Array = [23,0,32,45,56,75,43,0,34]; var Quicksort = function (arr) {if (arr.length <= 1) {return arr; } // Verifique el número de elementos en la matriz, si es menor o igual a 1, se devolverá. var pivotIndex = Math.floor (arr.length/2); // var pivot = arr.splice (pivotindex, 1) [0]; // seleccione "punto de referencia" (pivot) y separe de la matriz original, var izquierda = []; // Definir dos matrices vacías para almacenar dos subconjuntos de uno izquierdo y uno derecho VAR = []; para (var i = 0; i <arr.length; i ++) // transweep la matriz, coloque elementos más pequeños que el "punto de referencia" en el subconjunto de la izquierda y elementos más grandes que el punto de referencia en el subconjunto a la derecha. {if (arr [i] <pivot) {left.push (arr [i]); } else {right.push (arr [i]); }} return Quicksort (izquierda) .concat ([Pivot], Quicksort (derecha)); // Repita este proceso continuamente para obtener la matriz ordenada. }; var newArray = Quicksort (Array); console.log (newArray); <? Php $ array = [23,0,32,45,56,75,43,0,34]; función Quick_sort ($ arr) {// Primero determine si necesita continuar $ longitud = count ($ arr); if ($ longitud <= 1) {return $ arr; } $ base_num = $ arr [0]; // Seleccione una regla para seleccionar el primer elemento // Inicializar dos matrices $ Left_Array = Array (); // $ Right_array Menos que la regla = Array (); // for ($ i = 1; $ i <$ i+i ++) {// Transfiere todos los elementos excepto el ruler y ponerlos en dos matrices de acuerdo con el tamaño de la relación ($ sate $ arr [$ i]) {// Pon en la matriz izquierda $ Left_array [] = $ arr [$ i]; } else {// Poner a la derecha $ right_array [] = $ arr [$ i]; }} // Luego el mismo método de clasificación para las matrices izquierdo y derecha respectivamente // llamando a esta función de manera recursiva y registrando el resultado $ LEZT_Array = Quick_sort ($ LEZT_Array); $ right_array = Quick_sort ($ right_array); // fusionar la regla de la izquierda a la derecha array_merge ($ left_array, array ($ base_num), $ right_array); } $ newArray = Quick_Sort ($ Array); var_dump ($ newArray) ;?>5. Sorteo de la colina
Principio: Primero, divida toda la secuencia de registro para clasificarse en varias subsecutaciones para la inserción y clasificación directa. Cuando los registros en toda la secuencia se "ordenan básicamente", luego inserte y ordene los registros completos en secuencia. .
Complejidad del tiempo: Caso promedio: o (n√n) Mejor caso: o (nlog2n) peor caso: o (n2)
Complejidad del espacio: O (1)
Estabilidad: inestable
// JavaScript Hill Sort Var Array = [23,0,32,45,56,75,43,0,34]; var shellSort = function (arr) {var longitud = arr.length; var h = 1; while (h <longitud/3) {h = 3*h+1; // establecer intervalo} while (h> = 1) {for (var i = h; i <longitud; i ++) {for (var j = i; j> = h && arr [j] <jh]; j- = h) {var temp = arr [jh]; arr [jh] = arr [j]; arr [j] = temp; }} H = (H-1)/3; } return arr; } var newArray = shellSort (array); console.log (newArray); <? Php // Hill Sort $ Array = [23,0,32,45,56,75,43,0,34]; function shellSort ($ arr) {$ longitud = count ($ arr); $ H = 1; mientras ($ h <$ longitud/3) {$ h = 3*$ h+1; // set interval} while ($ h> = 1) {for ($ i = $ h; $ i <$ longitud; $ i ++) {for ($ j = $ i; $ j> = $ h && $ arr [$ j] <$ arr [j- $ h]; $ j-= $ h) {$ arr]; $ arr [$ j- $ h] = $ arr [$ j]; $ arr [$ j] = $ temp; }} $ h = ($ h-1)/3; } devolver $ arr; } $ newArray = shellSort ($ array); var_dump ($ newArray)?>6. Pedidos
Principio: Suponiendo que la secuencia inicial contiene n registros, se puede considerar como subsecuencias ordenadas, cada subsecuencia tiene una longitud de 1, y luego fusionada en pares para obtener (el entero más pequeño no menos que N/2) ordenó las posteriores con longitudes de 2 o 1, y se fusionó en pares ... repita esta forma hasta que se obtiene una secuencia ordenada con una longitud n.
Complejidad del tiempo: Caso promedio: O (NLOG2N) Mejor caso: O (NLOG2N) Peor Caso: O (NLOG2N)
Complejidad del espacio: O (1)
Estabilidad: establo
// JavaScript Merge Función de clasificación ISArray1 (arr) {if (object.prototype.ToString.call (arr) == '[Array de objetos]') {return true; } else {return false; }} function fuse (izquierda, derecha) {var resultado = []; if (! isarray1 (izquierda)) {izquierda = [izquierda]; } if (! isarray1 (right)) {right = [right]; } while (left.length> 0 && right.length> 0) {if (izquierda [0] <right [0]) {result.push (left.shift ()); } else {result.push (right.hift ()); }} return resultado.concat (izquierda) .concat (derecha); } función MergeSort (arr) {var len = arr.length; var lim, work = []; Var I, J, K; if (len == 1) {return arr; } para (i = 0; i <len; i ++) {work.push (arr [i]); } work.push ([]); para (lim = len; lim> 1;) {// lim es la longitud de agrupación para (j = 0, k = 0; k <lim; j ++, k = k+2) {work [j] = fusion (trabajo [k], trabajo [k+1]); } trabajo [j] = []; lim = math.floor ((lim+1)/2); } trabajo de retorno [0]; } var array = [23,0,32,45,56,75,43,0,34]; console.log (Mergesort (Array)); <? Php // Comprensión de la función de clasificación Mergesort (& $ arr) {$ len = count ($ arr); // Encontrar la longitud de la matriz msort ($ arr, 0, $ len-1); } // El programa que realmente implementa la función de clasificación de fusión msort (& $ arr, $ izquierda, $ rectificador) {if ($ left <$ right) {// indica que hay 1 elemento adicional en el subsecuencia, entonces es necesario dividir, clasificar por separado, fusionar // calcule la posición, longitud /2 vaya a todo $ center = piso ($ izquierdo+correcto) /2); // La llamada recursiva clasifica el lado izquierdo nuevamente: MSORT ($ arr, $ izquierda, $ centro); // llame recursivamente para ordenar el lado derecho nuevamente MSORT ($ arr, $ center+1, $ correcto); // fusionar los resultados de los sortes Mercarear ($ arr, $ izquierda, $ centro, $ correcto); }} // Combine dos números ordenados en una función de matriz ordenada Mercarear (& $ arr, $ izquierda, $ center, $ right) {// establece dos marcas de posición iniciales $ a_i = $ izquierda; $ B_i = $ Center+1; while ($ a_i <= $ center && $ b_i <= $ right) {// cuando ni la matriz a ni la matriz b cruza el límite if ($ arr [$ a_i] <$ arr [$ b_i]) {$ temp [] = $ arr [$ a_i ++]; } else {$ temp [] = $ arr [$ b_i ++]; }} // juzga si todos los elementos en la matriz A están agotados. Si no, inserte todos los elementos en la matriz c: while ($ a_i <= $ center) {$ temp [] = $ arr [$ a_i ++]; } // juzga si todos los elementos en la matriz B están agotados. Si no, inserte todos los elementos en la matriz c: while ($ b_i <= $ right) {$ temp [] = $ arr [$ b_i ++]; } // Escribe la parte ordenada en $ Arrc en $ arr: por ($ i = 0, $ len = count ($ temp); $ i <$ len; $ i ++) {$ arr [$ izquierda+$ i] = $ temp [$ i]; }} $ arr = array (23,0,32,45,56,75,43,0,34); Mergesort ($ arr); var_dump ($ arr) ;?>7. Clasificación de montón
Principio: la clasificación de montón es un método de clasificación utilizando el montón. La idea básica es: construir la secuencia que se clasificará en un montón superior grande. En este momento, el valor máximo de toda la secuencia es el nodo raíz de la parte superior del montón. Eliminarlo (de hecho, es intercambiarlo con el elemento final de la matriz de montón, y el elemento final es el valor máximo), y luego reconstruir las secuencias N-1 restantes en un montón, de modo que se obtenga el valor submáximo de N elementos. Esto dará como resultado una ejecución repetida y se puede obtener una secuencia ordenada.
Complejidad del tiempo: Caso promedio: O (NLOG2N) Mejor caso: O (NLOG2N) Peor Caso: O (NLOG2N)
Complejidad del espacio: O (1)
Estabilidad: inestable
// JavaScript Heap Sort Var Array = [23,0,32,45,56,75,43,0,34]; function HeApSort (array) {for (var i = math.floor (array.length / 2); i> = 0; i--) {HeapadJust (Array, I, Array.Length-1); // construir una matriz de matriz en un montón superior grande} para (i = array.length-1; i> = 0; i--) {/*intercambie el nodo raíz*/var temp = array [i]; matriz [i] = array [0]; matriz [0] = temp; /*La matriz restante continúa integrándose en un montón superior grande*/ Heapadjust (matriz, 0, i - 1); } matriz de retorno; } function Heapadjust (Array, Start, Max) {var temp = array [start]; // tempe es el valor del nodo raíz para (var j = 2 * start; j <max; j * = 2) {if (j <max && array [j] <j+1]) {// Obtener los hijos mayores ++ J; } if (temp> = array [j]) break; array [inicio] = array [j]; inicio = j; } array [inicio] = temp; } var newArray = HeApSort (Array); console.log (newArray); <? Php // Función de clasificación Heap HeApsort (& $ arr) {#initheap ($ arr, 0, count ($ arr) - 1); #Cambiar los nodos de cabeza y cola, y reduzca un nodo de extremo a la vez y ajuste el montón hasta que quede un elemento para ($ end = count ($ arr)-1; $ end> 0; $ end) {$ temp = $ arr [0]; $ arr [0] = $ arr [$ end]; $ arr [$ end] = $ temp; AjustNodes ($ arr, 0, $ end - 1); }} #Initialize el montón máximo, comience desde el último nodo no hojado, y el último nodo no hojado se numera como la función de longitud de matriz/2 redondeada initheap (& $ arr) {$ len = count ($ arr); para ($ start = piso ($ len / 2) - 1; $ start> = 0; $ start--) {aJustNodes ($ arr, $ start, $ len - 1); }}#Ajustarnodes#@param $ Arr Array se ajustará#@param $ iniciar las coordenadas del nodo principal que se ajustarán#@param $ end las coordenadas del nodo final se ajustará la función ajustnodes (& $ arr, $ start, $ end) {$ maxinx = $ start; $ len = $ end + 1; #La longitud de la pieza que se ajustará $ LeftChildInx = ($ Start + 1) * 2 - 1; #Left Child Coordinate $ rightchildinx = ($ start + 1) * 2; #Right Child Coordinate #Si la parte que se ajustará tiene un hijo izquierdo if ($ LeftChildInx + 1 <= $ len) {#get La coordenada de nodo mínimo if ($ arr [$ maxinx] <$ arr [$ leftchildinx]) {$ maxinx = $ leftchildinx; } #ISe la pieza que se ajustará tiene un nodo infantil correcto if ($ rightchildinx + 1 <= $ len) {if ($ arr [$ maxinx] <$ arr [$ rectildinx]) {$ maxinx = $ recthildinx; }}} #Swap nodo parent y nodo máximo if ($ start! = $ Maxinx) {$ temp = $ arr [$ start]; $ arr [$ start] = $ arr [$ maxinx]; $ arr [$ maxinx] = $ temp; #Se el nodo infantil Después del intercambio tiene nodos infantiles, continúe ajustándose if (($ 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. Clasificación de cardinalidad
Principio: Corte los enteros en diferentes números mediante dígitos y luego compárelos por separado por cada dígito. Dado que los enteros también pueden expresar cadenas (como nombres o fechas) y números de punto flotante en formatos específicos, la clasificación de radix no solo se usa para enteros.
Complejidad del tiempo: Caso promedio: O (D (R+N)) Mejor caso: O (D (N+RD)) Peor Caso: O (D (R+N)) R: Cardinalidad de palabras clave D: Longitud N: Número de palabras clave
Complejidad del espacio: O (RD+N)
Estabilidad: establo
<? Php #Blassorting, aquí solo se ordenan enteros positivos. En cuanto a los números negativos y los números de puntos flotantes, se necesita un complemento. Está interesado en estudiar #Counting Sort #@@Param $ Arr Array para estar ordenado #@param $ digit_num sort de acuerdo con el número de la función dígitos contando_sort (& $ arr, $ digit_num = false) {if ($ digit_num! == false) {#if el parámetro $ parámetro $ no está vacío, sorte según el número de $ digit_num digits of the element the el element ($ digits $ digit no está vacío, sorte según el número de $ digit_num digits of the element the el element ($ digits $ digit no está vacío. count ($ arr); }} else {$ arr_temp = $ arr; } $ max = max ($ arr); $ time_arr = array (); #Matriz de apartamentos de elementos#matriz de ocurrencias de inicialización para ($ i = 0; $ i <= $ max; $ i ++) {$ time_arr [$ i] = 0; } #Statice las ocurrencias de cada elemento para ($ i = 0; $ i <count ($ arr_temp); $ i ++) {$ time_arr [$ arr_temp); $ i ++) {$ time_arr [$ arr_temp [$ i]] ++; } #Statifica las ocurrencias de cada elemento que es más pequeño o igual a él para ($ i = 0; $ i <count ($ time_arr) - 1; $ i ++) {$ time_arr [$ i +1] += $ time_arr [$ i]; } #Sort la matriz usando el número de ocurrencias para ($ i = count ($ arr) - 1; $ i> = 0; $ i--) {$ sorted_arr [$ time_arr [$ arr_temp [$ i]] - 1] = $ arr [$ i]; $ Time_arr [$ arr_temp [$ i]]-; } $ arr = $ sorted_arr; ksort ($ arr); #Enignore La pérdida de eficiencia de la clasificación clave esta vez} #calcule el número de bits de una determinada función de número get_digit ($ number) {$ i = 1; while ($ number> = pow (10, $ i)) {$ i ++; } devolver $ i; } #get el número de dígito i -th de un número de la función de dígitos individuales get_specific_digit ($ num, $ i) {if ($ num <pow (10, $ i - 1)) {return 0; } piso de retorno ($ num % pow (10, $ i) / pow (10, $ i - 1)); } #Black Sorting, cuente la clasificación como una función de proceso de subsortación radix_sort (& $ arr) {#first Encuentre el dígito más grande en la matriz $ max = max ($ arr); $ max_digit = get_digit ($ max); para ($ i = 1; $ i <= $ max_digit; $ i ++) {counting_sort ($ arr, $ i); }} $ arr = array (23,0,32,45,56,75,43,0,34); radix_sort ($ arr); var_dump ($ arr) ;?>Lo anterior es todo el contenido de este artículo. Espero que sea útil para el aprendizaje de todos y espero que todos apoyen más a Wulin.com.