Exemples de code pour le tri par sélection en Java

Cet article présente principalement en détail des exemples de tri par sélection simple Java, qui ont une certaine valeur de référence. Les amis intéressés peuvent s'y référer

1 Concepts de base

Dans. à chaque passage, l'enregistrement avec le plus petit mot-clé est sélectionné parmi les enregistrements à trier, et l'ordre est placé à la fin de la séquence d'enregistrements triés jusqu'à ce que tout le tri soit terminé.

2. Idées de mise en œuvre

Rechercher l'élément avec le plus petit mot-clé de la séquence à trier
Si le plus petit élément n'est pas le premier élément de la séquence ; séquence à trier, échangez-la avec le premier élément
Parmi les N - 1 éléments restants, trouvez l'élément avec le plus petit mot-clé et répétez les étapes (1) et (2) jusqu'à ce que le tri soit terminé.

3. Implémentation du code

public class SelectionSort {

 public static void selectionSort(int[] list){
  //需要遍历获得最小值的次数
  if (1>=list.length)return;
  for (int i=0;i<list.length-1;i++){
   int temp=0;
   int index=i;  //选择当前值为最小值索引
   for (int j=i+1;j<list.length;j++){
    if (list[index]>list[j]){
     index=j; //修改最小值索引
    }
   }
   
   temp=list[index];
   list[index]=list[i];
   list[i]=temp;
  }
 }
 public static void main(String[] args){
  int[] list={4,3,6,5,7,8,2,10,2,9};
  selectionSort(list);
  for (int num:list){
   System.out.print(num+" ");
  }
 }
}

4. Le nombre de comparaisons pour le tri par sélection simple n'a rien à voir avec le tri initial de la séquence. En supposant que la séquence à trier comporte N éléments, le nombre de comparaisons est toujours N (N - 1) / 2.

Le nombre de coups est lié au tri initial de la séquence. Lorsque la séquence est dans l'ordre positif, le nombre de coups est le plus petit, soit 0.

Lorsque la séquence est dans l'ordre inverse, le nombre de coups est le plus grand, soit 3N (N - 1)/2.

Donc, sur la base de ce qui précède, la complexité temporelle d'un tri simple est O(N2).

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!