Tri de sélection simple: (sélectionnez la valeur minimale, mettez-la d'abord, puis le premier bit recule, donc Loop) Le premier bit se compare à chacun après le suivant, chaque fois que le plus petit bit est en tête, et le premier bit est en arrière La promotion (c'est-à-dire le premier chiffre qui vient d'être sélectionné est la valeur minimale, ne participe plus à la comparaison, le nombre de comparaisons est réduit de 1)
Complexité: le nombre d'opérations nécessaires pour effectuer un mouvement d'enregistrement est de 0 à 3 (N-1). / 2. La complexité du temps totale est O (n2);
Complexité de l'espace O (1)
Amélioration de l'algorithme: chaque fois que vous comparez, c'est pour mettre la plus petite valeur en premier lieu, afin que vous puissiez le comparer à la fin, trouver la valeur minimale et la mettre directement en premier lieu, éliminant les opérations de commutation et de déménagement dénuées de sens. Vous pouvez également modifier la direction, comparer le dernier bit avec chaque précédent et rendre la valeur maximale en bas à chaque fois et pousser le dernier bit vers l'avant.
Code source Java:
La copie de code est la suivante:
public static void selectSort (date [] jours) {
int min;
Date temporaire;
for (int i = 0; i <days.length; i ++) {
min = i;
pour (int j = min + 1; j <days.length; j ++) {
if (jours [min] .compare (jours [j])> 0) {
min = j;
}
}
si (min! = i) {
temp = jours [i];
jours [i] = jours [min];
jours [min] = temp;
}
}
}
Classe Date {
an, mois, mois, jour;
Date (int y, int m, int d) {
année = y;
mois = m;
jour = d;
}
public int compare (date de date) {
Retour année> Date.
: Mois> Date.mont?
: Jour> Date.Day? 1: Day <Date.Day?
}
public void print () {
System.out.println (année + "" + mois + "" + jour);
}
}
Sort de sélection simple:
Le tri de sélection simple est similaire au tri des bulles (tri à bulles). La seule différence est que le tri à bulles échange l'emplacement de l'élément chaque fois qu'il constate qu'il est plus petit (ou supérieur à celle) que la valeur actuelle, tandis que le tri de sélection simple est de sélectionner la plus valeur des éléments restants et d'échanger des données au niveau du Position actuelle.
Par exemple, pour les éléments définis r = {37, 40, 38, 42, 461, 5, 7, 9, 12}
Dans le premier ordre: 37 est directement échangé avec 5, formant une nouvelle séquence R1 = {5,40,38,42,461,37,7,9,12}
Dans le second ordre: 40 est directement échangé avec 7, formant une nouvelle séquence R2 = {5,7,38,42,461,37,40,9,12}
Et ainsi de suite jusqu'au dernier élément (Remarque: Dans le second ordre, 38 est inférieur à 42, mais ils n'échangent pas de données).
Voici une version d'implémentation Java qui sélectionne simplement le tri:
La copie de code est la suivante:
SELECTION STATIQUE STATIQUE PUBLIQUE (données int []) {
if (data == null || data.length <= 1)
retour;
int i, j, valeur, minpos, len = data.length;
int outer = len - 1, tmp;
pour (i = 0; i <extérieur; i ++) {
valeur = données [i];
minpos = -1;
pour (j = i + 1; j <len; j ++) {
if (data [j] <valeur) {
minpos = j;
valeur = données [j];
}
}
if (minpos! = -1) {
tmp = data [i];
data [i] = valeur;
data [minpos] = TMP;
}
// pour (int k = 0; k <len; k ++) {
// system.out.print (data [k] + ",");
//}
// System.out.println ();
}
}
public static void main (String [] args) {
int [] coll = {
37, 40, 38, 42, 461, 5, 7, 9, 12
};
SELECTIONATORT (COLL);
for (int i = 0; i <coll.length; i ++) {
System.out.print (coll [i] + ",");
}
}
Toi de sélection des arbres
L'algorithme de tri de sélection des arbres est un algorithme typique qui échange un espace contre le temps par rapport au tri de sélection simple. L'idée est de traiter les éléments N triés, de construire des nombres relativement petits (n + 1) / 2, puis de construire des nombres [n + 1] / 4 relativement petits jusqu'à ce qu'il n'y ait qu'un seul élément. Construit en un arbre complètement binaire.
Lors du tri, l'élément est le plus petit.
Voici une version de l'implémentation Java du tri des arbres:
La copie de code est la suivante:
public statique void Treeselectionsort (int [] data) {
if (data == null || data.length <= 1)
retour;
int len = data.length, Low = 0, i, j;
// Ajouter un espace auxiliaire
int [] tmp = new int [2 * len -1];
int tSize = tmp.length;
// construire un arbre
pour (i = len-1, j = tmp.length-1; i> = 0; i -, j -) {
tmp [j] = data [i];
}
pour (i = tSize -1; i> 0; i- = 2) {
tmp [(i-1) / 2] = tmp [i]> tmp [i-1]?
}
//fin
// Retirez le nœud minimum.
tandis que (bas <len) {
données [Low ++] = TMP [0];
pour (j = tsize-1; tmp [j]! = tmp [0]; j--);
tmp [j] = Integer.max_value;
while (j> 0) {
if (j% 2 == 0) {// s'il s'agit d'un nœud droit
tmp [(j-1) / 2] = tmp [j]> tmp [j-1]? tmp [j-1]: tmp [j];
j = (j-1) / 2;
} else {// Si c'est le nœud gauche
tmp [j / 2] = tmp [j]> tmp [j + 1]?
J = J / 2;
}
}
}
}
Lors de la construction d'un arbre binaire complet, un espace auxiliaire 2 * N -1 est nécessaire pour une collection de n éléments.
Code:
La copie de code est la suivante:
while (j> 0) {
if (j% 2 == 0) {// s'il s'agit d'un nœud droit
tmp [(j-1) / 2] = tmp [j]> tmp [j-1]? tmp [j-1]: tmp [j];
j = (j-1) / 2;
} else {// Si c'est le nœud gauche
tmp [j / 2] = tmp [j]> tmp [j + 1]?
J = J / 2;
}
}
Implémentez ensuite la construction récursive de la valeur minimale dans le nouvel ensemble.