Las entrevistas escritas a menudo involucran varios algoritmos. Este artículo presenta brevemente algunos algoritmos de uso común y los implementa en JavaScript.
1. Insertar clasificación
1) Introducción al algoritmo
La descripción del algoritmo de la clasificación de inserción es un algoritmo de clasificación simple e intuitivo. Funciona construyendo una secuencia ordenada, para datos no organizados, escanee hacia atrás y hacia adelante en la secuencia ordenada, encuentre la posición correspondiente e inserte. En la implementación de la clasificación de inserción, la clasificación en el lugar generalmente se usa (es decir, se requiere el espacio adicional de O (1)), por lo que durante el proceso de escaneo de regreso a delante, los elementos clasificados deben moverse repetidamente hacia atrás para proporcionar espacio de inserción para los últimos elementos.
2) Descripción e implementación del algoritmo
En términos generales, la clasificación de inserción se implementa en una matriz utilizando en el lugar. El algoritmo específico se describe de la siguiente manera:
A partir del primer elemento, se puede considerar que el elemento ha sido ordenado;
Saque el siguiente elemento y escanee hacia atrás y hacia adelante en la secuencia ya ordenada de elementos;
Si el elemento (ordenado) es mayor que el nuevo elemento, mueva el elemento a la siguiente posición;
Repita el paso 3 hasta que se encuentre el elemento ordenado donde el nuevo elemento es menor o igual;
Después de insertar un nuevo elemento en esa posición;
Repita los pasos 2 a 5.
Implementación del código JavaScript:
function InsertionSort (Array) {if (object.prototype.tostring.call (array) .slice (8, -1) === 'Array') {for (var i = 1; i <array.length; i ++) {var key = array [i]; var j = i - 1; while (j> = 0 && array [j]> key) {array [j + 1] = array [j]; J--; } matriz [j + 1] = clave; } matriz de retorno; } else {return 'la matriz no es una matriz!'; }}3) Análisis de algoritmo
El mejor de los casos: las matrices de entrada se clasifican en orden ascendente. T (n) = o (n)
El peor de los casos: la matriz de entrada se clasifica en orden descendente. T (n) = o (n2)
Promedio: t (n) = o (n2)
Dos, clasificación de inserción binaria
1) Introducción al algoritmo
La clasificación de clasificación de inserción binaria es un algoritmo de clasificación que realiza cambios menores en el algoritmo de clasificación de inserción directa. La mayor diferencia entre TI y el algoritmo de clasificación de inserción directa es que al buscar posiciones de inserción, se utiliza el método de búsqueda binaria, que tiene una cierta mejora en la velocidad.
2) Descripción e implementación del algoritmo
En términos generales, la clasificación de inserción se implementa en una matriz utilizando en el lugar. El algoritmo específico se describe de la siguiente manera:
A partir del primer elemento, se puede considerar que el elemento ha sido ordenado;
Saque el siguiente elemento y encuentre la posición del primer número más grande que en la secuencia de elementos ya ordenada;
Después de insertar un nuevo elemento en esa posición;
Repita los dos pasos anteriores.
Implementación del código JavaScript:
función binaryinsertionsort (array) {if (object.prototype.tostring.call (array) .slice (8, -1) === 'Array') {for (var i = 1; i <array.length; i ++) {var key = array [i], izquierda = 0, derecha = i - 1; while (izquierda <= derecha) {var middle = parseInt ((izquierda + derecha) / 2); if (key <array [middle]) {right = middle - 1; } else {izquierda = medio + 1; }} para (var j = i-1; j> = izquierda; j--) {array [j + 1] = array [j]; } matriz [izquierda] = clave; } matriz de retorno; } else {return 'la matriz no es una matriz!'; }}3) Análisis de algoritmo
El mejor caso: t (n) = o (nLogn)
El peor de los casos: t (n) = o (n2)
Promedio: t (n) = o (n2)
3. Seleccione la clasificación
1) Introducción al algoritmo
Selection-sort es un algoritmo de clasificación simple e intuitivo. Cómo funciona: primero encuentre el elemento más pequeño (grande) en la secuencia no organizada, guárdelo en la posición inicial de la secuencia ordenada, luego continúe buscando el elemento más pequeño (grande) de los elementos no organizados restantes, y luego colóquelo al final de la secuencia ordenada. Y así sucesivamente hasta que se clasifiquen todos los elementos.
2) Descripción e implementación del algoritmo
La selección directa de N registros se puede obtener a través de los pases N-1 para seleccionar y ordenar directamente. El algoritmo específico se describe de la siguiente manera:
Estado inicial: el área desordenada es R [1..N], y el área ordenada está vacía;
Cuando comienza el orden i-th (i = 1,2,3 ... N-1), las áreas actuales ordenadas y desordenadas son R [1..I-1] y R (i..n) respectivamente. Este orden selecciona el registro R [k] con la palabra clave más pequeña del área no ordenada actual, y la intercambia con el primer registro r del área no ordenada, de modo que R [1..i] y R [i+1..n) se convierten en un nuevo área ordenada con un aumento en el número de registros y un nuevo área no ordenada con una disminución en el número de registros;
El viaje N-1 termina y se ordena la matriz.
Implementación del código JavaScript:
función selectionsort (array) {if (object.prototype.tostring.call (array) .slice (8, -1) === 'Array') {var len = array.length, temp; para (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; }} matriz [i] = min; } matriz de retorno; } else {return 'la matriz no es una matriz!'; }}3) Análisis de algoritmo
El mejor caso: t (n) = o (n2)
El peor de los casos: t (n) = o (n2)
Promedio: t (n) = o (n2)
4. Clasificación de burbujas
1) Introducción al algoritmo
La clasificación de burbujas es un algoritmo de clasificación simple. Visita repetidamente las secuencias para clasificarse, compara dos elementos a la vez y los intercambia si son incorrectos. El trabajo de visitar la secuencia se repite hasta que no se necesita intercambio, es decir, la secuencia se ha ordenado. El origen de este algoritmo se debe a que cuanto más pequeño sea el elemento lentamente "flotará" en la parte superior de la secuencia a través del intercambio.
2) Descripción e implementación del algoritmo
El algoritmo específico se describe de la siguiente manera:
Compare elementos adyacentes. Si el primero es más grande que el segundo, intercambie dos de ellos;
Haga el mismo trabajo para cada par de elementos adyacentes, desde el comienzo del primer par hasta el final del último par, para que el último elemento sea el número más grande;
Repita los pasos anteriores para todos los elementos, excepto el último;
Repita los pasos 1 a 3 hasta que se complete la clasificación.
Implementación del código JavaScript:
function 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]; matriz [j] = array [j - 1]; matriz [j - 1] = temp; }}} matriz de retorno; } else {return 'la matriz no es una matriz!'; }}3) Análisis de algoritmo
El mejor caso: t (n) = o (n)
El peor de los casos: t (n) = o (n2)
Promedio: t (n) = o (n2)
5. Clasificación rápida
1) Introducción al algoritmo
La idea básica de la clasificación rápida: divida los registros para clasificarse en dos partes independientes a través de un orden, y las palabras clave de algunos registros son más pequeñas que las de la otra parte. Luego, los dos registros se pueden continuar clasificándolos por separado para lograr el orden de toda la secuencia.
2) Descripción e implementación del algoritmo
La clasificación rápida utiliza el método divisivo para dividir una cadena en dos subsistes. El algoritmo específico se describe de la siguiente manera:
Elegir un elemento de la secuencia se llama "principio" (pivote);
Vuelva a ordenar la secuencia, todos los elementos con más pequeños que el valor de referencia se colocan frente a la referencia, y todos los elementos con más grande que el valor de referencia se colocan detrás de la referencia (el mismo número se puede colocar a cada lado). Después de que esta partición sale, la referencia está en el medio de la secuencia. Esto se llama operación de partición;
Ordene recursivamente las subsecancaciones más pequeñas que el elemento de referencia y las subsecutivas más grandes que el elemento de referencia.
Implementación del código JavaScript:
// Método Una función QuickSort (Array, Left, Right) {if (Object.Protype.ToString.Call (Array) .slice (8, -1) === 'Array' && typeOf === '' Number '&& typeOf Derecho ===' Number ') {if (izquierdo <derecho) {var x = array [derecho], I = izquierda - 1, temperatorio; for (var j = izquierda; j <= right; j ++) {if (array [j] <= x) {i ++; temp = array [i]; matriz [i] = array [j]; matriz [j] = temp; }} Quicksort (matriz, izquierda, i - 1); Quicksort (matriz, i + 1, derecha); }; } else {return 'la matriz no es una matriz o izquierda o derecha no es un número!'; }} var aaa = [3, 5, 2, 9, 1]; Quicksort (aaa, 0, aaa.length - 1); console.log (aaa); // Método 2 var Quicksort = function (arr) {if (arr.length <= 1) {return arr; } var pivotIndex = math.floor (arr.length / 2); var pivot = arr.splice (pivotindex, 1) [0]; var izquierda = []; var right = []; for (var i = 0; i <arr.length; i ++) {if (arr [i] <pivot) {left.push (arr [i]); } else {right.push (arr [i]); }} return Quicksort (izquierda) .concat ([Pivot], Quicksort (derecha)); };3) Análisis de algoritmo
El mejor caso: t (n) = o (nLogn)
El peor de los casos: t (n) = o (n2)
Promedio: t (n) = o (nLogn)
6. Clasificación de montón
1) Introducción al algoritmo
La clasificación del montón se refiere a un algoritmo de clasificación diseñado utilizando la estructura de datos del montón. El apilamiento es una estructura que es aproximadamente completamente binaria y satisface las propiedades del apilamiento: es decir, el valor clave o el índice de un nodo secundario siempre es más pequeño que (o mayor que) su nodo principal.
2) Descripción e implementación del algoritmo
El algoritmo específico se describe de la siguiente manera:
La secuencia inicial de palabras clave a ordenar (R1, R2 ... RN) se construye en un montón superior grande, que es el área inicial desordenada;
Intercambie el elemento superior del montón R [1] con el último elemento R [n], y en este momento, se obtiene una nueva región desordenada (R1, R2, ... RN-1) y una nueva región ordenada (RN), y R [1,2 ... N-1] <= R [n] se satisface;
Dado que el nuevo montón superior R [1] después del intercambio puede violar las propiedades del montón, es necesario ajustar el área actual no ordenada (R1, R2, ... RN-1) al nuevo montón, y luego intercambiar R [1] con el último elemento del área no ordenada nuevamente para obtener un nuevo área no ordenada (R1, R2 ... RN-2) y un nuevo área ordenada (RN-1, RN). Repita este proceso hasta que el número de elementos en el área ordenada sea N-1, y se completa todo el proceso de clasificación.
Implementación del código JavaScript:
/*Descripción del método: sort de articulación @param array para ordenarse*/function HeapSort (array) {if (object.prototype.ToString.call (array) .slice (8, -1) === 'Array') {// build Heap Varsize = Array.length, temp; for (var i = math.floor (Heapsize / 2); i> = 0; i--) {Heapify (Array, I, HeepSize); } // sort de montón para (var j = HeepSize-1; j> = 1; j--) {temp = array [0]; matriz [0] = array [j]; matriz [j] = temp; HeApify (matriz, 0, --alteapSize); }} else {return 'Array no es una matriz!'; }}/* Method description: Maintain the properties of the heap @param arr Array @param x Array Subscript @param len Heap size*/function heapify(arr, x, len) { if (Object.prototype.toString.call(arr).slice(8, -1) === 'Array' && typeof x === 'number') { var l = 2 * x, r = 2 * x + 1, más grande = x, temp; if (l <len && arr [l]> arr [más grande]) {más grande = l; } if (r <len && arr [r]> arr [más grande]) {más grande = r; } if (más grande! = x) {temp = arr [x]; arr [x] = arr [más grande]; arr [más grande] = temp; Heapify (arr, grande, len); }} else {return 'arr no es una matriz o x no es un número!'; }}3) Análisis de algoritmo
El mejor caso: t (n) = o (nLogn)
El peor de los casos: t (n) = o (nLogn)
Promedio: t (n) = o (nLogn)
7. Pedidos
1) Introducción al algoritmo
La clasificación de fusión es un algoritmo de clasificación efectivo basado en la operación de fusión. Este algoritmo es una aplicación muy típica de divide y conquista. La clasificación de fusión es un método de clasificación estable. Fusionar las subsecuencias ordenadas para obtener una secuencia completamente ordenada; Es decir, haga cada subsecuencia de primer orden y luego haga orden de segmentos subsecuencias. Si dos tablas ordenadas se fusionan en una tabla ordenada, se llama fusión de 2 vías.
2) Descripción e implementación del algoritmo
El algoritmo específico se describe de la siguiente manera:
Divida la secuencia de entrada de longitud n en dos subsecuencias de longitud n/2;
Estas dos subsecuencias se clasifican juntas por separado;
Fusionar las dos subsecuencias ordenadas en una secuencia ordenada final.
Implementación del código JavaScript:
función mergsort (array, p, r) {if (p <r) {var q = math.floor ((p + r) / 2); Mergesort (Array, P, Q); Mergesort (matriz, q + 1, r); fusionar (matriz, p, q, r); }} función fusion (array, p, q, r) {var n1 = q - p + 1, n2 = r - q, izquierda = [], derecha = [], m = n = 0; for (var i = 0; i <n1; i ++) {izquierda [i] = array [p+i]; } para (var j = 0; j <n2; j ++) {right [j] = array [q + 1 + j]; } izquierda [n1] = derecha [n2] = number.max_value; for (var k = p; k <= r; k ++) {if (izquierda [m] <= right [n]) {array [k] = izquierda [m]; m ++; } else {array [k] = right [n]; n ++; }}}3) Análisis de algoritmo
El mejor caso: t (n) = o (n)
El peor de los casos: t (n) = o (nLogn)
Promedio: t (n) = o (nLogn)
8. Clasificación de cubos
1) Introducción al algoritmo
El principio de clasificación de cubos: suponiendo que los datos de entrada se distribuyan uniformemente, los datos se dividen en un número limitado de cubos, y cada cubo se clasifica por separado (es posible usar otros algoritmos de clasificación o continuar utilizando la clasificación de cubos de manera recursiva).
2) Descripción e implementación del algoritmo
El algoritmo específico se describe de la siguiente manera:
Establezca una matriz cuantitativa como un cubo vacío;
Iterar a través de los datos de entrada y colocar los datos en el cubo correspondiente uno por uno;
Ordene cada cubo que no esté vacío;
Empalde los datos ordenados de un cubo vacío.
Implementación del código JavaScript:
/*Descripción del método: sort de bucket @param array array @param num número de cubos*/ function bucketSort (array, num) {if (array.length <= 1) {return array; } var len = array.length, buckets = [], resultado = [], min = max = array [0], regex = '/^[1-9]+[0-9]*$/', espacio, n = 0; num = num || ((num> 1 && regex.test (num))? Num: 10); para (var i = 1; i <len; i ++) {min = min <= array [i]? min: matriz [i]; max = max> = array [i]? max: matriz [i]; } space = (máx - min + 1) / num; for (var j = 0; j <len; j ++) {var index = math.floor ((array [j] - min) / space); if (buckets [index]) {// bucket no vacío, inserte el ordenar var k = buckets [index] .length - 1; while (k> = 0 && buckets [index] [k]> array [j]) {buckets [index] [k + 1] = buckets [index] [k]; K--; } cubos [índice] [k + 1] = array [j]; } else {// bucket vacío, inicializar cubos [index] = []; cubos [índice] .push (matriz [j]); }} while (n <num) {resultado = resultado.concat (cubos [n]); n ++; } resultado de retorno; }3) Análisis de algoritmo
En el mejor de los casos de clasificación de cubos, tiempo lineal O (n), la complejidad del tiempo de la clasificación de cubos depende de la complejidad del tiempo de la clasificación de los datos entre los cubos, porque la complejidad del tiempo de otras partes es o (n). Obviamente, cuanto más pequeño se divide el cubo, menos datos son el cubo, menos tiempo tarda en ordenarlo. Pero el consumo de espacio correspondiente aumentará.
9. Contando clasificación
1) Introducción al algoritmo
El tipo de contar es un algoritmo de clasificación estable. La clasificación de recuento usa una matriz adicional C, donde el elemento I-Th es el número de elementos con un valor igual a I en la matriz A para ser ordenado. Luego, según Array C, los elementos en A están dispuestos a la posición correcta. Solo puede ordenar enteros.
2) Descripción e implementación del algoritmo
El algoritmo específico se describe de la siguiente manera:
Encuentre los elementos más grandes y más pequeños de la matriz para ser ordenados;
Cuente el número de veces que aparece cada elemento con un valor de I en la matriz y guárdelo en el i-them de matriz c;
Acumular todos los recuentos (a partir del primer elemento en C, cada elemento y el elemento anterior se agregan);
Matriz de destino de relleno inverso: coloque cada elemento I en el elemento C (i) th de la nueva matriz, y reste C (i) por 1 para cada elemento.
Implementación del código JavaScript:
function countingsort (array) {var len = array.length, b = [], c = [], min = max = array [0]; para (var i = 0; i <len; i ++) {min = min <= array [i]? min: matriz [i]; max = max> = array [i]? max: matriz [i]; C [matriz [i]] = c [matriz [i]]? C [matriz [i]] + 1: 1; } para (var j = min; j <max; j ++) {c [j + 1] = (c [j + 1] || 0) + (c [j] || 0); } para (var k = len - 1; k> = 0; k--) {b [c [array [k]] - 1] = array [k]; C [matriz [k]]-; } retorno b; }3) Análisis de algoritmo
Cuando el elemento de entrada es n enteros entre 0 y k, su tiempo de ejecución es O (n + k). La clasificación de recuento no es una clasificación de comparación, y la velocidad de clasificación es más rápida que cualquier algoritmo de clasificación de comparación. Dado que la longitud de la matriz C utilizada para contar depende del rango de datos en la matriz a clasificar (igual a la diferencia entre los valores máximos y mínimos de la matriz a clasificar más 1), esto hace que la clasificación de recuento requiere mucho tiempo y memoria para matrices con un rango de datos amplio.