Classificação rápida, também conhecida como particionamento e classificação de troca. Um algoritmo de classificação rápida implementada com a estratégia de dividir e conquistar.
Este artigo fala principalmente sobre o uso do JavaScript para implementar a classificação rápida de idéias no local
Dividir e tratar métodos:
Na ciência da computação, o método de divisão e conquista é um paradigma de algoritmo muito importante com base na recursão de múltiplas filiais. A explicação literal é "dividir e conquistar", o que significa dividir um problema complexo em dois ou mais subproblemas idênticos ou semelhantes até que o final do subproblema possa ser resolvido de maneira simples e diretamente, e a solução do problema original é a fusão das soluções do sub-problema. (Trecho da Wikipedia)
Ideia rápida de classificação
Especifique um elemento na matriz como régua, coloque o maior que ele e coloque o menor que antes do elemento, repita -o até que todos estejam dispostos na ordem positiva.
A classificação rápida é dividida em três etapas:
Selecione um benchmark: selecione um elemento como referência na estrutura de dados (pivô)
Partição: consulte o tamanho do valor do elemento de referência, divida a área não ordenada. Todos os dados menores que o elemento de referência são colocados em um intervalo, e todos os dados maiores que o elemento de referência são colocados em outro intervalo. Após a conclusão da operação de partição, a posição do elemento de referência é a posição em que deve estar após a classificação final.
Recursão: chame recursivamente os algoritmos na etapa 1 e 2 pela primeira vez até que haja apenas um elemento restante em todos os intervalos não ordenados.
Agora vamos falar sobre os métodos de implementação comum (nenhum algoritmo no local é usado)
function quicksort (arr) {if (arr.length <= 1) return; // Por favor, o benchmark de dígitos mais próximo do meio da matriz, números ímpares e números até os valores são diferentes, mas acho que não. Obviamente, você pode escolher o primeiro ou o último número como referência, e não há muita descrição aqui var pivotIndex = math.floor (arr.length/2); var pivot = arr.splice (pivotIndex, 1) [0]; // intervalos esquerdos e esquerda são usados para armazenar os números classificados var = [] []; (var i = 0; i <arr.length; i ++) {console.log ('o' + (i + 1) + 'loop da operação de partição:'); // há menos do que a referência, coloque no intervalo esquerdo, maior que a referência, coloque o intervalo direito se (ar. {right.push (arr [i]); console.log ('direita:' + (arr [i]))}} // O operador concat é usado aqui para unir o intervalo, referência e intervalo direito de esquerda) e depois de um novo elemento (e o recursivo, o retorno do recursivo Recursive 1 e 2 e 2 e 2 e o Recursive Retters Retterns Retwork e o Return Retters Retwork e 2 e 2 e 2 e 2 e 2 e 2 e as devoluções e as devoluções e as devoluções e as devoluções e as devoluções e as devoluções e as devoluções mais rápidas. Quicksort (direita));} var arr = [14, 3, 15, 7, 2, 76, 11]; Console.log (Quicksort (arr));/** Quando a base é 7, a primeira partição é obtida com dois subconjuntos e à esquerda [3, 2, 2 [14, 15, 76, 11]; All sorting of the left subset ends* With the reference as 76, the right subset is divided and sorted to obtain [14, 15, 11] 76* At this time, the above [14, 15, 11] is divided and sorted to the above [14, 15, 11] is divided and sorted to the above [14, 11] is divided and sorted to the above [14, 11] is divided and sorted to the above [14, 11] is divided and sorted to O acima [14, 11] é dividido e classificado para o acima [11] é dividido e classificado para a base 11, 11 [14]*Há apenas um elemento restante em todos os intervalos não ordenados, e a extremidade recursiva **/Através da depuração do ponto de interrupção, os resultados podem ser obtidos.
Desvantagens:
Requer espaço de armazenamento extra de ω (n), o que é tão ruim quanto a classificação de mesclagem. Em um ambiente de produção, é necessário espaço de memória adicional, afetando o desempenho.
Ao mesmo tempo, muitas pessoas pensam que o exposto acima é um tipo muito rápido. Portanto, abaixo, é necessário recomendar a classificação rápida do algoritmo no local
Para obter informações sobre o algoritmo in situ, consulte a Wikipedia. Os alunos que estão sob o muro são semelhantes ao Baidu.
no local
A classificação rápida é geralmente implementada com recursão. O mais importante é a função de segmentação de partição, que divide a matriz em duas partes, uma é menor que o pivô e a outra é maior que o pivô. O princípio específico foi mencionado acima
função quicksort (arr) {// troca de função Swap (arr, a, b) {var temp = arr [a]; arr [a] = arr [b]; arr [b] = temp;} // Partição de partição Partição (ARR, à esquerda, direita) {/*** No começo, você não sabe o local de referência final, que pode trocar a direita) {/*** no começo*que você não sabe o local de referência do pivador, a direita, a direita) {/*** no começo*que você não sabe o que se referente, a direita, a direita, a direita, a direita, a direita, a direita para a direita para a direita para a direita para a direita para a direita) {/*** no começo, você não sabe o local de referência final, que pode servir à esquerda) {/*** = arr [direita];/*** Ao armazenar elementos menores que o pivô, eles estão próximos ao elemento anterior; caso contrário, o elemento armazenado na lacuna pode ser maior que o pivô,*, portanto, uma variável da loja é declarada e inicializada para armazenar elementos menores que o pivô um ao lado um do outro. */var storeIndex = esquerda; para (var i = esquerda; i <direita; i ++) {if (arr [i] <pivot) {/*** Atravesse a matriz e encontre o elemento menor que o pivô (elementos maiores que o pivô serão ignorados)* colocar o elemento obtido quando o loop -t para o IndindEx até a troca de troca, e a troca* e a troca*. trocado*/swap (arr, storeIndex, i); storeIndex ++;}} // finalmente: trocar o pivô para armazenar o StoreIndex, coloque o elemento de benchmark na troca final de posição correta (arr, direita, storeIndex); retorno armazeneiro; 1); classificar (arr, storeIndex + 1, direita);} classificar (arr, 0, arr.length - 1); retornar arr;} console.log (Quicksort ([8, 4, 90, 8, 34, 67, 1, 26, 17]));Otimização de partição
Os alunos cuidadosos aqui podem perguntar se haverá desempenho diferente ao selecionar diferentes benchmarks. A resposta é sim, mas porque sou uma pessoa de front-end e não sei muito sobre o algoritmo, então este poço é deixado para pessoas poderosas para preencher.
Complexidade
A classificação rápida é o algoritmo de classificação mais rápido, e sua complexidade de tempo é O (log n)
Na situação média, a ordem dos n itens requer comparações (n log n). Na pior das hipóteses, são necessárias comparações (n2).
https://github.com/lyz0106/
O exposto acima é o método de classificação rápida da implementação de JavaScript, idéias no local introduzidas pelo editor. Espero que seja útil para todos. Se você tiver alguma dúvida, deixe -me uma mensagem. O editor responderá a tempo. Muito obrigado pelo seu apoio ao site da Wulin Network!