La idea de "clasificación rápida" es muy simple, y todo el proceso de clasificación solo requiere tres pasos:
(1) En el conjunto de datos, seleccione un elemento como "base" (pivote).
(2) todos los elementos más pequeños que la "referencia" se mueven a la izquierda de la "referencia"; Todos los elementos más grandes que la "referencia" se mueven a la derecha de la "referencia".
(3) Para los dos subconjuntos a la izquierda y a la derecha de la "línea de base", repita los primeros y segundos pasos hasta que solo quede un elemento en todos los subconjuntos.
Por ejemplo, ahora hay un conjunto de datos {85, 24, 63, 45, 17, 31, 96, 50}. ¿Cómo ordenarlo?
En el primer paso, seleccione el elemento intermedio 45 como la "base". (El valor de referencia se puede seleccionar arbitrariamente, pero elegir el valor intermedio es más fácil de entender).
El segundo paso es comparar cada elemento con la "base" para formar dos subconjuntos, uno es "menos de 45" y el otro es "mayor o igual a 45".
El tercer paso es repetir el primer y segundo paso para los dos subconjuntos hasta que solo quede un elemento en todos los subconjuntos.
La siguiente es una referencia a la información en línea (aquí y aquí) para implementar el algoritmo anterior en el idioma JavaScript.
Primero, defina una función rápida cuyos parámetros son una matriz.
var Quicksort = function (arr) {};Luego, verifique el número de elementos en la matriz, y si es menor o igual a 1, se devolverá.
var Quicksort = function (arr) {if (arr.length <= 1) {return arr; }};A continuación, seleccione "Pivot" y separe de la matriz original, y luego defina dos matrices vacías para almacenar dos subconjuntos de uno a la izquierda y otro derecho.
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 = [];};Luego, comience a atravesar la matriz, coloque elementos más pequeños que la "base" en el subconjunto de la izquierda y elementos más grandes que la base en el subconjunto a la derecha.
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]); }}};Finalmente, repita este proceso continuamente utilizando la recursión para obtener la matriz ordenada.
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));};Al usarlo, simplemente llame a Quicksort ().
Lo anterior es una explicación detallada del ejemplo del algoritmo QuickSort de la serie de algoritmo JavaScript introducido por el editor. Espero que te sea útil. Si tiene alguna pregunta, déjame un mensaje y el editor le responderá a tiempo. ¡Muchas gracias por su apoyo al sitio web de Wulin.com!