Classificação simples de seleção: (selecione o valor mínimo, coloque -o em primeiro Promover (ou seja, o primeiro dígito selecionado é o valor mínimo, não mais participa da comparação, o número de comparações é reduzido por 1)
Complexidade: o número de operações necessárias para executar o movimento de registro é 0-3 (n-1). / 2. A complexidade total do tempo é O (n2);
Complexidade espacial o (1)
Melhoria do algoritmo: toda vez que você compara, é para colocar o menor valor em primeiro lugar, para que você possa compará -lo até o final, encontrar o valor mínimo e colocá -lo diretamente em primeiro lugar, eliminando operações sem sentido e sem sentido. Você também pode alterar a direção, comparar o último bit com cada um anterior e fazer com que o valor máximo seja inferior a cada vez e empurre o último bit para a frente.
Java Código fonte:
A cópia do código é a seguinte:
public static void selectSort (data [] dias) {
int min;
Data de data;
for (int i = 0; i <dias.length; i ++) {
min = i;
for (int j = min+1; j <dias.length; j ++) {
if (dias [min] .compare (dias [j])> 0) {
min = j;
}
}
if (min! = i) {
temp = dias [i];
dias [i] = dias [min];
dias [min] = temp;
}
}
}
Data da classe {
int ano, mês, dia;
Data (int y, int m, int d) {
ano = y;
mês = m;
dia = d;
}
public int compare (data) {
Ano de retorno> Data.Year?
: mês> DAT.MONTH?
: dia> DATA.DAY?
}
public void print () {
System.out.println (ano + "" + mês + "" + dia);
}
}
Classificação de seleção simples:
O tipo de seleção simples é semelhante à classificação de bolhas (classificação de bolhas). A única diferença é que a classificação de bolhas troca a localização do elemento toda vez que achar que é menor (ou maior que) que o valor atual, enquanto a simples classificação de seleção é selecionar o maior valor nos elementos restantes e trocar dados no posição atual.
Por exemplo, para o conjunto de elementos r = {37, 40, 38, 42, 461, 5, 7, 9, 12}
Na primeira ordem: 37 é trocada diretamente com 5, formando uma nova sequência r1 = {5,40,38,42,461,37,7,9,12}
Na segunda ordem: 40 é trocada diretamente com 7, formando uma nova sequência r2 = {5,7,38,42,461,37,40,9,12}
E assim por diante até o último elemento (Nota: na segunda ordem, 38 é menor que 42, mas eles não trocam dados).
Aqui está uma versão de implementação do Java que simplesmente seleciona a classificação:
A cópia do código é a seguinte:
public static void SelectionSort (int [] dados) {
if (data == null || data.length <= 1)
retornar;
int i, j, value, minpos, len = data.length;
int Outer = len - 1, tmp;
for (i = 0; i <Outer; i ++) {
valor = dados [i];
minpos = -1;
for (j = i+1; j <len; j ++) {
if (dados [j] <valor) {
minpos = j;
valor = dados [j];
}
}
if (Minpos! = -1) {
tmp = dados [i];
dados [i] = valor;
dados [MinPOS] = TMP;
}
// para (int k = 0; k <len; k ++) {
// system.out.print (dados [k] + ",");
//}
// System.out.println ();
}
}
public static void main (string [] args) {
int [] coll = {
37, 40, 38, 42, 461, 5, 7, 9, 12
};
Selectionsort (Coll);
for (int i = 0; i <coll.length; i ++) {
System.out.print (coll [i] + ",");
}
}
Seleção de árvores
O algoritmo de classificação de seleção de árvores é um algoritmo típico que negocia espaço pelo tempo em comparação com a simples classificação de seleção. A idéia é tratar os n elementos classificados, construir números relativamente pequenos (n+1)/2 e depois construir números relativamente pequenos [n+1]/4 até que haja apenas um elemento. Construído em uma árvore completamente binária.
Ao classificar, o elemento é o menor.
Aqui está uma versão de implementação de Java da seleção de árvores classificando:
A cópia do código é a seguinte:
public static void TreeSelectionSort (int [] dados) {
if (data == null || data.length <= 1)
retornar;
int len = data.length, baixo = 0, i, j;
// Adicionar espaço auxiliar
int [] tmp = new int [2*len -1];
int tsize = tmp.length;
// Construa uma árvore
for (i = len-1, j = tmp.length-1; i> = 0; i-, j-) {
tmp [j] = dados [i];
}
for (i = tsize -1; i> 0; i- = 2) {
tmp [(i-1)/2] = tmp [i]> tmp [i-1]?
}
//fim
// Remova o nó mínimo.
while (baixo <len) {
dados [baixo ++] = tmp [0];
for (j = tsize-1; tmp [j]! = tmp [0]; j--);
tmp [j] = Integer.max_value;
while (j> 0) {
if (j%2 == 0) {// se for um nó certo
tmp [(j-1)/2] = tmp [j]> tmp [j-1]? tmp [j-1]: tmp [j];
j = (J-1)/2;
} else {// se for o nó esquerdo
tmp [j/2] = tmp [j]> tmp [j+1]?
j = j/2;
}
}
}
}
Ao construir uma árvore binária completa, é necessário um espaço auxiliar de 2*n -1 para uma coleção de n elementos.
Código:
A cópia do código é a seguinte:
while (j> 0) {
if (j%2 == 0) {// se for um nó certo
tmp [(j-1)/2] = tmp [j]> tmp [j-1]? tmp [j-1]: tmp [j];
j = (J-1)/2;
} else {// se for o nó esquerdo
tmp [j/2] = tmp [j]> tmp [j+1]?
j = j/2;
}
}
Em seguida, implemente a construção recursiva do valor mínimo no novo conjunto.