1. Visão geral
Classificação e pesquisa são dois problemas básicos de programação, e existem muitos algoritmos clássicos usados para resolver esses dois tipos de problemas. Este artigo conduz principalmente uma discussão básica sobre a implementação de algoritmos de classificação em Java, na esperança de servir como ponto de partida. papel. Antes disso, deixe-me primeiro fazer algumas perguntas: Você consegue escrever uma classificação rápida correta? Em que circunstâncias a classificação rápida é realmente rápida? Sua fila rápida é rápida o suficiente? Pode ser otimizado ainda mais? Com essas questões, vamos dar uma olhada em como a classificação rápida é implementada no jre7.
A classe de implementação de classificação no Jre7 é DualPivotQuickSort.java. Em comparação com o jre6, há algumas mudanças, principalmente em dois lugares. Um é a implementação da classificação por inserção e o outro é que o pivô na implementação do QuickSort muda de um para dois. . Vamos pegar um array do tipo int como exemplo. Existe um método principal para implementação de classificação nesta classe.
Copie o código do código da seguinte forma:
void sort(int[] a, int esquerda, int direita, booleano mais à esquerda)
O parâmetro a é o array que precisa ser classificado, a esquerda representa o índice do elemento mais à esquerda no intervalo do array que precisa ser classificado, a direita representa o índice do elemento mais à direita no intervalo e o mais à esquerda representa se o intervalo é o mais à esquerda intervalo na matriz. Por exemplo:
Matriz: [2, 4, 8, 5, 6, 3, 0, -3, 9] pode ser dividida em três intervalos (2, 4, 8){5, 6}<3, 0, -3, 9>
Para intervalo (), esquerda = 0, direita = 2, mais à esquerda = verdadeiro
Para o intervalo {}, left=3, right=4, leftmost=false, os parâmetros correspondentes do intervalo <> podem ser obtidos da mesma maneira.
Quando o comprimento do intervalo for menor que 47, este método usará a classificação por inserção, caso contrário, a classificação rápida será usada;
2. Implementação de classificação por inserção
Quando mais à esquerda for verdadeiro, ele usará a classificação de inserção tradicional e o código é relativamente simples. O processo é semelhante a pegar e inserir cartas ao jogar cartas:
Copie o código do código da seguinte forma:
for (int i = esquerda, j = i; i < direita; j = ++i) {
int ai = a[i + 1];
enquanto (ai < a[j]) {
uma[j + 1] = uma[j];
if (j-- == esquerda) {
quebrar;
}
}
uma[j + 1] = ai;
}
Código de classificação de inserção tradicional
Quando mais à esquerda é falso, ele usa um novo tipo de classificação por inserção (classificação por inserção de pares). A melhoria é que cada vez que ele percorre a matriz classificada anteriormente, dois elementos precisam ser inseridos, enquanto a classificação por inserção tradicional requer apenas Encontre um local adequado para. um elemento a ser inserido. Para a ordenação por inserção, a chave é encontrar uma posição de inserção adequada para o elemento a ser inserido. Para encontrar esta posição, é necessário percorrer o subarray previamente ordenado, portanto, para a ordenação por inserção, os elementos que ele percorre durante toda a ordenação. processo O número determina seu desempenho. Obviamente, inserir dois elementos em cada travessia pode reduzir o número de elementos percorridos durante o processo de classificação. O código de implementação é o seguinte:
Copie o código do código da seguinte forma:
for (int k = esquerda; ++esquerda <= direita; k = ++esquerda) {
int a1 = a[k], a2 = a[esquerda];
se (a1 <a2) {
a2 = a1; a1 = a[esquerda];
}
enquanto (a1 <a[--k]) {
uma[k + 2] = uma[k];
}
uma[++k + 1] = a1;
enquanto (a2 <a[--k]) {
uma[k + 1] = uma[k];
}
uma[k + 1] = a2;
}
Agora há uma pergunta: por que o intervalo mais à esquerda usa a classificação por inserção tradicional e os outros usam a classificação por inserção aos pares? Que problemas surgirão se substituirmos o código de classificação por inserção tradicional pelo código de classificação por inserção em pares acima? Espero que todos vocês respondam sozinhos. . .
3. Implementação de classificação rápida
A classificação rápida também foi aprimorada no Jre7. A classificação rápida tradicional seleciona um pivô (os métodos jre6 de seleção do pivô consistem em selecionar os elementos nas posições mais à esquerda, no meio e mais à direita da matriz e classificar os elementos com os valores do meio como. pivô) e, em seguida, atravesse de ambas as extremidades para o meio e coloque os objetos encontrados durante a travessia à esquerda O valor maior que o pivô é trocado pelo valor menor ou igual ao pivô encontrado no percurso à direita. Quando o percurso se encontra, o valor do pivô é inserido, isso torna os valores à esquerda do pivô menores que ou; igual ao pivô e o valor à direita do pivô é maior que o pivô continue Em seguida, use a recursão para classificar os lados esquerdo e direito, respectivamente;
Através da análise acima, podemos ver que: cada etapa da classificação por inserção é tornar um subintervalo da matriz absolutamente ordenado, e a essência de cada ciclo é expandir continuamente esse subintervalo, para que possamos ver que a direção da otimização é para make Cada travessia de loop faz com que o subintervalo se expanda o mais rápido possível, portanto, a otimização acima de inserir um elemento por travessia na inserção de dois elementos por vez é otimizada. Claro, alguém certamente perguntará: por que não aumentar esse número? Por exemplo, 5 ou 10 são inseridos cada vez que é percorrido. . . Obviamente, isso não é possível. Um caso extremo é inserir n itens (n é o comprimento do array) cada vez que ele é percorrido. . . Quanto ao porquê, cada um pode responder por si mesmo.
Para ordenação rápida, o que cada recursão faz é fazer com que os subintervalos que precisam ser ordenados fiquem mais ordenados, ao invés de ordenados de forma absoluta; portanto, para ordenação rápida, seu desempenho depende de como cada operação recursiva faz com que o subintervalo seja ordenado de forma mais ordenada; O determinante do grau em que um subintervalo se torna ordenado é, obviamente, o número de recursões. A chave para a classificação rápida para tornar o subintervalo relativamente ordenado é o pivô, portanto, a direção de nossa otimização também deve ser o pivô. Em seguida, aumente o número de pivôs e descobriremos que aumentar o número de pivôs não afeta o número de pivôs. recursões Terá um grande impacto e às vezes pode até reduzir o número de recursões. Uma pergunta semelhante à classificação por inserção é: quantos pivôs devem ser aumentados? Obviamente, o valor do pivô não pode ser muito grande, lembre-se, qualquer otimização tem um custo, e o custo de aumentar o pivô fica oculto no processo de troca de posição dos elementos a cada vez; Guanzi parece ser vendido um pouco demais. . . Vamos dar uma olhada em como a classificação rápida é implementada quando o valor do pivô é 2. Na verdade, seu processo de implementação não é difícil de entender:
1. Primeiro selecione dois pivôs. O método de seleção de pivô consiste em dividir a matriz em seis segmentos de igual comprimento. Esses seis segmentos são, na verdade, separados por 5 elementos. 4º, como pivot1 e pivot2 respectivamente;
2. Depois que o Pivô for selecionado, percorra das extremidades esquerda e direita até o meio. A condição de parada para o percurso à esquerda é encontrar um valor maior ou igual ao pivô1 e marcar essa posição como menor; travessia é encontrar um valor menor ou igual ao valor do pivô2 e marcar essa posição como ótima
3. Em seguida, percorra para trás a partir da posição inferior. A posição percorrida é representada por k.
a. Se o valor da posição k for menor que o pivô1, então troque os valores da posição k e da posição menor e adicione 1 ao valor menor, isso fará com que os valores fiquem à esquerda do; menor posição menor que pivô1, e os valores entre a posição menor e a posição k serão O valor é maior ou igual a pivô1
b. Se o valor na posição k for maior que o pivô2, então percorra da posição grande para a esquerda. A condição de parada para o percurso é encontrar um valor menor ou igual ao pivô2. este valor para a posição menor e escreva o valor na posição menor. O valor é escrito como a posição k, e o valor da posição k é escrito como a posição ótima e, finalmente, menos++, ótimo - adicione este valor. para ser maior ou igual ao pivô1, troque a posição k e a posição ótima e, em seguida, ótimo-
4. Após concluir o processo acima, o subintervalo classificado é dividido em três segmentos (<pivot1, pivot1<=&&<=pivot2,>pivot2). Finalmente, a recursão é usada para esses três segmentos.
Copie o código do código da seguinte forma:
/*
* Particionamento:
*
* parte esquerda parte central parte direita
* +------------------------------------------------ ---------------+
* | < pivô1 | pivô1 <= && <= pivô2 |
* +------------------------------------------------ ---------------+
* ^ ^ ^
* |
*menos k ótimo
*
*Invariantes:
*
* all in (esquerda, menos) < pivot1
* pivô1 <= tudo em [menos, k) <= pivô2
* all in (ótimo, certo) > pivot2
*
* O ponteiro k é o primeiro índice da parte ?.
*/
O conteúdo principal da implementação de classificação no Jre7 é mencionado acima. Para detalhes específicos, consulte o código na classe correspondente. Se você encontrar algum erro ou inadequação, corrija-o.