Prefácio: O tópico das estruturas e algoritmos de dados Java será atualizado de tempos em tempos. Os leitores podem supervisioná -lo. Este artigo começa com o algoritmo de classificação mais simples - classificação do balde e analisa as idéias de implementação, implementação de código, características de desempenho e cenários aplicáveis de classificação de baldes.
0. Outros índices de algoritmo de classificação
//www.vevb.com/article/120879.htm
1. Ideia de classificação do balde
Um exemplo simples:
Classificando as pontuações dos testes em inglês de 6 pessoas (1 ~ 10 pontos). If the score is [6, 5, 8, 8, 10, 9], the idea of sorting with buckets is to prepare 10 buckets, the numbers are 1~10 in sequence, and the scores are placed in the corresponding buckets, such as 6 points into the No. 6 bucket, and two 8 points into the No. 8 bucket... and then output them one by one according to the order of the bucket numbers (if there is, if there is, if there is no one, no output). Esta é a idéia básica da classificação do balde.
De fato, esta é apenas uma versão simples. Imagine, se a faixa de span de elementos a serem classificados for relativamente grande, como 1 ~ 10.000, você precisa de 10.000 baldes? De fato, neste caso, um elemento nem sempre é colocado em um balde, mas muitas vezes vários elementos são colocados em um balde. De fato, a lista real de classificação e hash de baldes têm o mesmo princípio.
Na classificação real, os elementos em cada balde geralmente são classificados usando outros algoritmos de classificação; portanto, mais frequentemente, a classificação do balde é usada em combinação com outros algoritmos de classificação.
2. Código de classificação do balde
Depois de analisar a idéia de classificação do balde, você deve primeiro conhecer a gama de elementos a serem classificados. Tomando o exposto como exemplo, declare uma matriz de comprimento 10 como 10 baldes e, em seguida, coloque os resultados um por um no balde, o valor do balde é +1 e, finalmente, produza o subscrito da matriz em ordem inversa. O valor de cada posição da matriz é emitido várias vezes, para que o tipo básico de balde possa ser alcançado.
public class BucketSort {private int [] baldes; Private Int [] Array; public bucketsort (intervalo int, int [] Array) {this.buckets = new int [intervalo]; this.array = matriz; } /*Classificação* / public void Sort () {if (Array! = Null && Array.length> 1) {for (int i = 0; i <Array.length; i ++) {Buckets [Array [i]]] ++; }}}/*Classificação de saída*/public void Sortout () {// Dados de saída reversa para (int i = buckets.length-1; i> = 0; i-) {for (int j = 0; j <buckets [i]; j ++) {System.out.print (i+"/t"); }}}}Código de teste:
public class SortTest {public static void main (string [] args) {testbucketSort (); } private estático void testBucketSort () {int [] Array = {5,7,3,5,4,8,6,4,1,2}; Bucketsort bs = novo bucketsort (10, matriz); bs.sort (); Bs.Sortout (); // Classificação de impressão de saída}}3. Características de desempenho de classificação do balde
A classificação do bucket requer apenas a iteração por todos os elementos a serem classificados e, em seguida, colocá -los na posição especificada em sequência. Se o tempo de classificação de saída for adicionado, todos os baldes precisarão ser atravessados. Portanto, a complexidade do tempo da classificação do balde é O (n+m), n é o número de elementos a serem classificados e M é o número de baldes, ou seja, a gama de elementos a serem classificados. Esse algoritmo é um algoritmo de classificação muito rápido, mas a complexidade espacial é relativamente grande.
Quando a faixa de tamanho de elementos a serem organizados é relativamente grande, mas o número de elementos a serem organizados é relativamente pequeno, o desperdício espacial é mais grave. A distribuição de elementos a serem organizados é uniforme a cada mês, e quanto maior a taxa de utilização de espaço, isso é realmente raro.
Através da análise de desempenho acima, podemos obter as características da classificação do balde: rápida e simples, mas, ao mesmo tempo, a utilização do espaço é baixa. Quando os dados a serem classificados são grandes, a taxa de utilização de espaço é insuportável.
4. Cenários de classificação de balde aplicáveis
De acordo com as características da classificação do balde, a classificação do balde geralmente é aplicável a alguns ambientes específicos, como o intervalo de dados é relativamente limitado ou existem alguns requisitos específicos, como a necessidade de obter rapidamente certos valores através do mapeamento de hash e o número de cada número precisa ser contado. Mas tudo isso é baseado na confirmação do escopo dos dados. Se a extensão do escopo for muito grande, considere o uso de outros algoritmos.