Principe et mise en œuvre de l'algorithme de tri par sélection simple JAVA

Tri par sélection simple : (sélectionnez la plus petite valeur, placez-la en premier, puis déplacez la première valeur vers l'arrière, et ainsi de suite) Comparez la première valeur avec chacune des suivantes, une par une, et placez la plus petite valeur en haut de chacune temps. Les bits sont repoussés vers l'arrière (c'est-à-dire que le premier bit qui vient d'être sélectionné est la valeur minimale et n'est plus impliqué dans la comparaison, et le nombre de comparaisons est réduit de 1)

Complexité : Le nombre de les opérations requises pour déplacer l'enregistrement sont inférieures à 0--3 (n-1), quelle que soit la disposition initiale des enregistrements, le nombre de comparaisons requises entre les mots-clés est le même, soit n(n-1)/2, et la complexité temporelle totale est O(n2);
Complexité spatiale O(1)

Amélioration de l'algorithme : chaque comparaison consiste à mettre la plus petite valeur en premier, afin que vous puissiez la comparer jusqu'à la fin, trouver la plus petite valeur, et placez-la directement en premier lieu. Éliminez les opérations d'échange et de déplacement inutiles. Vous pouvez également changer la direction et comparer le dernier bit avec chaque précédent, en faisant descendre la valeur maximale vers le bas à chaque fois et en faisant avancer le dernier bit.

Code source JAVA :

 public static void selectSort(Date[] days) {
  int min;
  Date temp;
  for (int i = 0; i < days.length; i++) {
   min = i;
   for (int j = min + 1; j < days.length; j++) {
    if (days[min].compare(days[j]) > 0) {
     min = j;
    }
   }
   if (min != i) {
    temp = days[i];
    days[i] = days[min];
    days[min] = temp;
   }
  }
 }
class Date {
 int year, month, day;
 Date(int y, int m, int d) {
  year = y;
  month = m;
  day = d;
 }
 public int compare(Date date) {
  return year > date.year ? 1 : year < date.year ? -1
    : month > date.month ? 1 : month < date.month ? -1
      : day > date.day ? 1 : day < date.day ? -1 : 0;
 }
 public void print() {
  System.out.println(year + " " + month + " " + day);
 }
}

Tri par sélection simple :

Le tri par sélection simple est similaire au tri à bulles, il fonctionnera à chaque fois Sélectionnez la valeur la plus élevée parmi les valeurs restantes élément défini et remplissez-le dans la position actuelle. La seule différence est que le tri à bulles échangera la position de l'élément chaque fois qu'il constate qu'elle est inférieure (ou supérieure à) la valeur actuelle, tandis que le tri par sélection simple sélectionne la valeur la plus élevée parmi les éléments restants et échange des données avec la valeur actuelle. position.

　Par exemple, pour l'ensemble d'éléments R={37, 40, 38, 42, 461, 5, 7, 9, 12>

　Au premier passage de tri : 37 est directement échangé avec 5, Former une nouvelle séquence R1={5,40,38,42,461,37,7,9,12}
Dans le deuxième tri : 40 est directement échangé avec 7 pour former une nouvelle séquence R2={5, 7, 38,42,461,37,40,9,12}

et ainsi de suite jusqu'au dernier élément (remarque : lors de la deuxième passe de tri, 38 est plus petit que 42, mais ils n'échangent pas de données) .

Ce qui suit est une version d'implémentation Java du tri par sélection simple :

　　public static void selectionSort（int[] data） {
　　if （data == null || data.length <= 1）
　　return;
　　int i, j, value, minPos, len = data.length;
　　int outer = len - 1, tmp;
　　for （i = 0; i < outer; i++） {
　　value = data[i];
　　minPos = -1;
　　for （j = i + 1; j < len; j++） {
　　if （data[j] < value） {
　　minPos = j;
　　value = data[j];
　　}
　　}
　　if （minPos != -1） {
　　tmp = data[i];
　　data[i] = value;
　　data[minPos] = tmp;
　　}
　　//            for （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
　　};
　　selectionSort（coll）；
　　for （int i = 0; i < coll.length; i++） {
　　System.out.print（coll[i] + " , "）；
　　}
　　}

Tri par sélection d'arbre (Tree Selection Sort)
L'algorithme de tri par sélection d'arbre est typique par rapport au tri par sélection simple Algorithme d'échange d'espace contre du temps. L'idée est de traiter les N éléments triés, de construire des nombres relativement petits (n 1)/2, puis de construire des nombres relativement petits [n 1]/4 jusqu'à ce qu'il n'y ait qu'un seul élément. Construit dans un arbre binaire complet.
Lors du tri, l'élément est le plus petit. Retirez le plus petit élément, remplacez l'élément par la "valeur maximale", puis ajustez l'arbre binaire complet.
Ce qui suit est une implémentation Java du tri par sélection d'arbre :

　　public static void treeSelectionSort（int[] data） {
　　if （data == null || data.length <= 1）
　　return;
　　int len = data.length , low = 0 , i , j;
　　// add Auxiliary Space
　　int[] tmp = new int[2*len -1];
　　int tSize = tmp.length;
　　//construct a tree
　　for（i =len-1 , j=tmp.length-1;i >=0 ;i--,j--）{
　　tmp[j]=data[i];
　　}
　　for（i = tSize -1 ; i > 0 ; i-=2）{
　　tmp[（i-1）/2] = tmp[i] > tmp[i-1]? tmp[i-1]:tmp[i];
　　}
　　//end
　　//remove the minimum node.
　　while（low < len）{
　　data[low++] = tmp[0];
　　for（j=tSize-1;tmp[j]!=tmp[0];j--）；
　　tmp[j] = Integer.MAX_VALUE;
　　while（j > 0）{
　　if（j%2 == 0）{  //如果是右节点
　　tmp[（j-1）/2] = tmp[j] > tmp[j-1]?tmp[j-1]:tmp[j];
　　j = （j-1）/2;
　　}else{  //如果是左节点
　　tmp[j/2]=tmp[j] > tmp[j+1]? tmp[j+1]:tmp[j];
　　j = j/2;
　　}
　　}
　　}
　　}

Lors de la construction d'un arbre binaire complet, un ensemble de N éléments nécessite 2*N -1 espace auxiliaire.
Code :

　　while（j > 0）{
　　if（j%2 == 0）{  //如果是右节点
　　tmp[（j-1）/2] = tmp[j] > tmp[j-1]?tmp[j-1]:tmp[j];
　　j = （j-1）/2;
　　}else{  //如果是左节点
　　tmp[j/2]=tmp[j] > tmp[j+1]? tmp[j+1]:tmp[j];
　　j = j/2;
　　}
　　}

implémente la construction récursive de la valeur minimale dans le nouvel ensemble.

Pour plus d'articles liés au principe et à la mise en œuvre de l'algorithme de tri par sélection simple JAVA, veuillez faire attention au site Web PHP chinois !