Exemple de didacticiel sur l'implémentation d'un algorithme de tri par sélection en Java

Concept de tri par sélection

Le tri par sélection est également un algorithme de tri par échange et présente une certaine similitude avec le tri à bulles. Par conséquent, je pense personnellement que le tri par sélection peut être considéré comme un algorithme amélioré de tri à bulles. L'idée est la suivante :
Supposons maintenant que nous voulions trier le tableau arr[], qui comporte n éléments.
1 Comparez le premier élément (en Java, l'indice est 0) et le deuxième élément. Si le premier est supérieur au second, alors il ne doit pas être le plus petit, mais nous ne sommes pas aussi anxieux que l'échange de tri à bulles. Nous pouvons définir une variable temporaire a pour stocker l'indice du plus petit élément actuel. Ensuite, nous continuons à comparer le plus petit élément actuel avec le troisième élément. Si ce n'est toujours pas le plus petit, alors nous modifions la valeur de a. De cette façon, jusqu'à ce que la comparaison avec le dernier élément soit terminée, vous pouvez être sûr que a stocke l'indice du plus petit élément.
2. Si la valeur de a n'est pas 0 (valeur initiale, c'est-à-dire l'indice du premier élément), échangez les deux éléments avec les indices a et 0.
3. Répétez le processus ci-dessus, cette fois en commençant par l'élément avec l'indice 1, car le plus petit élément est déjà placé à la position avec l'indice 0.
4. Faites cela jusqu'à ce qu'il ne reste que le dernier élément. Vous pouvez être sûr que cet élément est le plus grand.
5. Tri terminé.
Évidemment, cet algorithme nécessite également n-1 tours de tri.
Il convient de noter que ce qui précède n'est qu'une méthode pour trouver la valeur minimale à chaque fois. En fait, vous pouvez également trouver la valeur maximale à chaque fois, mais vous devez ensuite la mettre à la fin du tableau à chaque fois.

Code d'implémentation Java :
SelectArray.java

package ch02;
 
public class SelectArray {
  // 数组
  private long[] arr;
 
  // 数组中有效数据的大小
  private int elems;
 
  // 默认构造函数
  public SelectArray() {
    arr = new long[50];
  }
 
  public SelectArray(int max) {
    arr = new long[max];
  }
 
  // 插入数据
  public void insert(long value) {
    arr[elems] = value;
    elems++;
  }
 
  // 显示数据
  public void display() {
    for (int i = 0; i < elems; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }
 
  // 选择排序
  public void selectSort(){
    int min = 0;
    long tmp = 0L;
    for(int i = 0; i < elems -1; i++){
      min = i;
      for(int j = i + 1; j < elems; j++) {
        if(arr[j] < arr[min]) {
          min = j;
        }
      }
      tmp = arr[i];
      arr[i] = arr[min];
      arr[min] = tmp;
    }
  }
}

Code de test :

package ch02;
 
public class TestSelectArray {
 
  public static void main(String[] args) {
    SelectArray sArr = new SelectArray();
    sArr.insert(89);
    sArr.insert(54);
    sArr.insert(667);
    sArr.insert(7);
    sArr.insert(12);
    sArr.insert(43);
    sArr.insert(12);
 
    sArr.display();
    sArr.selectSort();
    sArr.display();
 
  }
 
}

Résultat :

Pour plus d'articles connexes sur l'implémentation Java de didacticiels d'exemple d'algorithme de tri par sélection, veuillez faire attention au site Web PHP chinois !