Idéias básicas
O RadixSort é desenvolvido com base na classificação do balde, e ambas as classificações são implementações avançadas para alocar a classificação. A idéia básica do distribuinte: o processo de classificação não requer comparação de palavras -chave, mas implementa a classificação dos processos "distribuição" e "coletar". Sua complexidade de tempo pode atingir uma ordem linear: O (n).
A classificação da cardinalidade é um algoritmo de classificação estável, mas tem certas limitações:
1. Palavras -chave podem ser decompostas.
2. O número de palavras -chave registradas é menor e é melhor se forem densas. 3. Se for um número, é melhor não ser assinado, caso contrário, a complexidade do mapeamento correspondente será aumentada. Você pode primeiro classificá -los separadamente.
Vamos dar uma olhada na classificação do balde (Radixsort).
A classificação do balde também é chamada de classificação de caixa (Binsort). Sua idéia básica é configurar vários baldes, digitalizar os registros a serem classificados r [0], r [1],…, r [n-1], carregar todos os registros com palavras-chave em um determinado intervalo no KTH Bucket (alocado) e depois conectar as cabeças e as caudas de cada balde não vazio (colecionar) de acordo com o número de sequência.
Por exemplo, para classificar 52 cartas de jogo embaralhadas por pontos A <2 <… <j <q <k, 13 "baldes" precisam ser definidos. Ao classificar, cada cartão é colocado no balde correspondente por pontos e, em seguida, os baldes são conectados em sequência para organizar um baralho de cartas em ordem incremental de pontos.
Na classificação do balde, o número de baldes depende do intervalo de valor da palavra -chave. Portanto, a classificação do balde requer que o tipo de palavra -chave seja finito, caso contrário, baldes ilimitados podem ser necessários.
De um modo geral, é imprevisível quantos registros com as mesmas palavras -chave são armazenados em cada balde, para que o tipo de balde deve ser projetado como uma lista vinculada.
Para garantir que a classificação seja estável, as conexões durante o processo de embalagem e coleta devem ser realizadas de acordo com o primeiro princípio da primeira saída.
Para a classificação do balde, o tempo do processo de alocação é O (n); O tempo do processo de coleta é O (M) (uma lista vinculada é usada para armazenar os registros de entrada a ser classificada) ou O (M+N). Portanto, o tempo para a classificação do balde é O (M+N). Se a ordem de magnitude do número de baldes m for O (n), o tempo da classificação do balde é linear, ou seja, O (n).
Na maioria das vezes, a complexidade dos principais algoritmos de classificação mencionada acima é O (n2), e alguns algoritmos de classificação são O (nLogn). Mas a classificação do barril pode atingir a complexidade do tempo de O (n). No entanto, as desvantagens da classificação do balde são: Antes de tudo, a complexidade do espaço é relativamente alta e a sobrecarga adicional é necessária. A classificação tem duas matrizes de espaço no alto, uma armazena a matriz a ser classificada e a outra é o chamado balde. Por exemplo, o valor a ser classificado é de 0 a M-1, então os baldes M são necessários e essa matriz de balde requer pelo menos o espaço M. Em segundo lugar, os elementos a serem classificados devem estar dentro de um determinado intervalo, etc.
A classificação da cardinalidade é uma melhoria na classificação do balde, o que torna a "classificação do balde" adequada para conjuntos maiores de valores de elementos, em vez de melhorar o desempenho.
Vamos usar o exemplo de jogo de cartas para ilustrar. Um cartão consiste em duas palavras -chave: nitir (pêssego <coração <mei <quadrado) + valor de face (a <2 <3 <4 <... <k). Se o tamanho de um cartão for determinado pelo processo primeiro e os cartões do mesmo traje serão determinados pelo número. Temos dois algoritmos para resolver esse problema.
Ou seja, se os fatos forem diferentes, não importa qual seja o valor nominal, o cartão com uma cor mais baixa é menor que a cor do terno com uma cor mais alta. Somente na mesma cor do traje, a relação tamanho é determinada pelo tamanho do valor da face. Esta é a ordem de vários códigos -chave.
Para obter resultados de classificação, discutimos dois métodos de classificação.
Método 1: Primeiro, classifique os ternos e cores e divida -os em 4 grupos, ou seja, grupo de flores de ameixa, grupo quadrado, grupo cardíaco vermelho e grupo cardíaco preto. Em seguida, classifique cada grupo pelo valor de face e, finalmente, conecte os 4 grupos.
Método 2: Primeiro, forneça 13 grupos de números (nº 2, 3, ..., a) De acordo com 13 valores de face, coloque os cartões nos grupos de números correspondentes em ordem de acordo com os valores da face e os divida em 13 pilhas. Em seguida, dê 4 grupos de numeração (flores de ameixa, quadrados, corações vermelhos, corações pretos), retire os cartões do Grupo 2 e os coloque no grupo correspondente de cor e, em seguida, retire os cartões do Grupo 3 e os coloque no grupo correspondente de cores ... dessa maneira, todos os 4 grupos de cores são ordenados de acordo com o valor face e, em seguida, os 4 grupos de cores nas seqüências.
A classificação de código com várias teclas é classificada em ordem do código-chave principal para o segundo código-chave ou da segunda chave para o código-chave principal, e é dividido em dois métodos:
A prioridade de bits mais significativa (MostSignificantDigitfirst), referida como o método MSD:
1) Primeiro classifique e agrupe -os por K1, divida a sequência em várias subsequências. Nos registros do mesmo grupo de seqüências, os códigos -chave K1 são iguais.
2) Em seguida, classifique cada grupo em subgrupos por K2. Depois disso, continue a classificar os seguintes códigos de chave dessa maneira até que cada subgrupo seja classificado pelo código -chave mais secundário KD.
3) Em seguida, conecte os grupos para obter uma sequência ordenada. O método introduzido em cartões de classificação por ações e valores de face é o método MSD.
O método menos significativo do Método, referido como o método LSD:
1) Comece a classificar do KD e classifique o KD-1, repetindo por sua vez até que seja dividido na menor subsequência de acordo com o K1.
2) Finalmente, conecte cada sub-sequência para obter uma sequência ordenada. O segundo método introduzido em cartões de classificação por traje e valor de face é o método LSD.
Uma única palavra-chave de um tipo numérico ou de caractere pode ser considerado como uma palavra de teclado composta por vários dígitos ou vários caracteres. Neste momento, o método "Allocation-Collect" pode ser usado para classificá-lo. Esse processo é chamado de método de classificação da cardinalidade, onde o número de valores possíveis para cada número ou caractere é chamado de cardinalidade. Por exemplo, a base de ternos de cartas de jogo é 4 e a base do valor nominal é 13. Ao classificar as cartas de jogo, você pode organizá -las pelo estilo primeiro ou pelo valor nominal primeiro. Ao classificar de acordo com as cores, primeiro divida -o em 4 pilhas (distribuições) na ordem de vermelho, preto, quadrado e flores, depois as empilhem (colete) nessa ordem e divida -as em 13 pilhas (distribuições) na ordem de valor nominal e depois empilhe -as (coleta) nesta ordem. Dessa forma, a alocação e a coleção secundárias podem organizar as cartas de uma maneira ordenada.
Durante o processo de "coleta de alocação", a estabilidade da classificação precisa ser garantida.
A idéia de classificação da cardinalidade é investigar cada grupo de palavras -chave nos dados a serem classificados em sequência. Por exemplo, a seguinte sequência a ser classificada:
135, 242, 192, 93, 345, 11, 24, 19
Dividimos o único, dez e centenas de dígitos de cada valor em três palavras -chave, por exemplo:
135-> k1 (dígitos únicos) = 5, k2 (dez dígitos) = 3, k3 (cem dígitos) = 1.
Em seguida, inicie a partir do menor bit mais baixo (começando pela última palavra-chave), todas as palavras-chave K1 de todos os dados são alocadas em balde (porque cada número é 0-9, portanto o tamanho do balde é 10) e, em seguida, produza os dados no balde em sequência para obter a sequência a seguir.
(11), (242, 192), (93), (24), (135, 345), (19) (classificação a partir da palavra -chave mais -chave, ignorando os cem e dez dígitos e alocando de acordo com os números nos dígitos únicos)
Então a sequência acima é alocada para K2, e a sequência de saída é:
(11, 19), (24), (135), (242, 345), (192, 93) (consulte a palavra -chave mais para classificar a segunda palavra -chave, ignorar as cem e dígitos e alocar de acordo com o número nos dez dígitos)
Finalmente, para a alocação de balde do K3, a sequência de saída é:
(011, 019, 024, 093), (135, 192), (242), (345) (consulte a segunda palavra -chave para classificar a palavra -chave mais alta, ignorar os dez e únicos dígitos e alocá -los de acordo com os números nos cem dígitos)
A classificação está completa.
Implementação de Java
public void radixsort () {int max = matriz [0]; for (int i = 0; i <Array.Length; i ++) {// Encontre o valor máximo na matriz if (matriz [i]> max) {max = matriz [i]; }} int keysnum = 0; // O número de palavras -chave, usamos dígitos, dez dígitos e centenas ... como palavras -chave, portanto o número de palavras -chave é o dígito máximo enquanto (máximo> 0) {max /= 10; keysnum ++; } List <ArrayList <Teger>> buckets = new ArrayList <ArrayList <Teger>> (); for (int i = 0; i <10; i ++) {// O número possível para cada dígito é 0 ~ 9, então defina 10 baldes de baldes.add (novo ArrayList <Teger> ()); // O balde é composto de ArrayList <Teger>} para (int i = 0; i <keysnum; i ++) {// Comece com a palavra -chave mais recente, atribua -a de acordo com as palavras -chave por sua vez para (int jelem elementos; como 258. Agora você precisa retirar o número nos dez dígitos, 258%100 = 58,58/10 = 5 int -chave = array [j]%(int) math.pow (10, i+1)/(int) math.pow (10, i); buckets.get (key) .add (matriz [j]); // Coloque esse elemento em um balde com a chave de palavra -chave} // Após a alocação, copie os elementos no balde de volta para a matriz int contat = 0; // contador de elementos para (int j = 0; j <10; j ++) {ArrayList <Teger> bucket = buckets.get (j); // bucket com palavra -chave j while (bucket.size ()> 0) {array [contador ++] = bucket.remove (0); // copie o primeiro elemento no balde para a matriz e remova}} System.out.print ("Thread"+(i+1)+"Classificação da roda:"); mostrar(); }}Os resultados da impressão são os seguintes:
Análise de algoritmo
À primeira vista, a eficiência da execução do tipo de cardinalidade parece ser boa e é inacreditável que tudo o que você precise fazer é copiar os itens de dados originais da matriz para a lista vinculada e copiá -los de volta. Se houver 10 itens de dados, existem 20 repetições, repetindo o processo para cada bit. Supondo que os números de 5 dígitos sejam classificados, 20*5 = 100 cópias são necessárias. Se houver 100 itens de dados, existem 200*5 = 1000 cópias. O número de cópias é proporcional ao número de itens de dados, ou seja, O (n). Este é o algoritmo de classificação mais eficiente que vimos.
Infelizmente, quanto mais itens de dados, as palavras -chave mais longas são necessárias. Se os itens de dados forem aumentados 10 vezes, a palavra -chave deverá ser adicionada por uma (mais uma rodada de classificação). O número de cópias e o número de itens de dados são proporcionais ao comprimento da palavra -chave, e pode -se considerar que o comprimento da palavra -chave é o logaritmo de N. Portanto, na maioria dos casos, a eficiência da execução da classificação cardinal é revertida para O (n*logn), o que é quase o mesmo como classificação rápida.
Resumir
O exposto acima é o conteúdo inteiro deste artigo sobre a introdução à classificação da cardinalidade e a implementação do idioma Java. Espero que seja útil para todos. Amigos interessados podem continuar se referindo a outros tópicos relacionados neste site. Se houver alguma falha, deixe uma mensagem para apontá -la.