Algorithme de tri de structure de données Java (3) tri par sélection simple

Cet article présente principalement la simplicité des structures de données et des algorithmes Java Tri par sélection, et analyse les principes, les méthodes de mise en œuvre et les techniques de fonctionnement associées du tri par sélection sous forme d'exemples auxquels les amis dans le besoin peuvent se référer. it

Les exemples de cet article décrivent un tri par sélection simple des structures de données et des algorithmes Java. Je le partage avec vous pour votre référence. Les détails sont les suivants :

Dans l'article précédent, nous avons déjà décrit l'algorithme de tri de la classe d'échange. Dans cette section, nous commencerons à parler du tri. algorithme de la classe de sélection. Tout d'abord, jetons un coup d'œil à l'algorithme de tri par sélection :

Idée algorithmique de base du tri par sélection :

Chaque voyage est en n-i+1 (i=1,2, sélectionnez l'enregistrement avec le plus petit mot-clé parmi 3,...,n-1) enregistrements comme i-ème enregistrement dans la séquence ordonnée.

Tri par sélection simple :

Supposons que le nombre d'enregistrements dans la séquence triée soit n. je prends 1,2,…,n-1, trouve l'enregistrement avec le plus petit code de tri parmi tous les n-i+1 enregistrements (Ri, Ri+1,…,Rn) et l'échange avec le i-ème enregistrement. Après avoir exécuté n-1 fois, le tri de la séquence d'enregistrements est terminé.

Le code d'implémentation de l'algorithme est le suivant :

package exp_sort;
public class SimpleSelectSort {
  static int i;
  static int temp;
  public static void selectSort(int array[]) {
    for (i = 0; i < array.length; i++) {
      int k = i;  //记录当前位置
      for (int j = i + 1; j < array.length; j++) {
        if (array[j] < array[k]) {   //找出最小的数，并用k指向最小数的位置
          k = j;
        }
      }
            //交换最小数array[k]与第i位上的数
      if (k != i) {
        temp = array[i];
        array[i] = array[k];
        array[k] = temp;
      }
    }
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    selectSort(array);
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("\n");
  }
}

Analyse de l'algorithme :

Au cours de ce processus de tri, les enregistrements doivent être déplacés. Le nombre de fois est relativement faible. Dans le meilleur des cas, c'est-à-dire que l'état initial des enregistrements à trier est déjà dans l'ordre positif, il n'est pas nécessaire de déplacer les enregistrements ; dans le pire des cas, c'est-à-dire que l'état initial des enregistrements à trier est ; dans l'ordre inverse, le nombre maximum de coups requis est : 3 (n-1). Le nombre de comparaisons requises pendant le processus de tri n'a rien à voir avec la disposition de la séquence d'enregistrements à trier dans l'état initial. Lorsque i=1, n-1 comparaisons sont requises ; lorsque i=n, ​​​​le nombre total de comparaisons requises est : n(n-1)/2, c'est-à-dire que la complexité temporelle de l'opération de comparaison est : O( n^ 2), la complexité temporelle de l'opération de déplacement est O(n) ; ce tri est

tri instable .

[Recommandations associées]

1.

algorithme de tri de structure de données Java (1) tri par sélection d'arbre

2.

Tri de structure de données Java. algorithme (2) Tri par fusion

3

Tutoriel détaillé sur le tri par sélection (Selection Sort_java) en Java

4.

Algorithme de tri de la structure des données Java. (4) Tri de sélection

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!