A) Principe : Chaque fois, sélectionnez le plus petit élément dans les enregistrements à tri et placez-le dans l'ordre à la fin de la séquence triée jusqu'à ce que tous les enregistrements soient triés. C'est-à-dire que chaque voyage est sélectionné comme i-tth enregistrement dans la séquence ordonnée entre les enregistrements N-I + 1 (i = 1, 2, ... n-1). Les algorithmes basés sur cette idée incluent principalement le tri de sélection simple, le tri de sélection des arbres et le tri des tas. (Ceci est un tri de sélection simple uniquement)
b) L'idée de base de la sélection simple de tri : étant donné un tableau: int [] arr = {n data dedans}; La première fois, sélectionnez les plus petites données des données à tri ARR [1] ~ ARR [n] et échangez-les avec ARR [1]; La deuxième fois, sélectionnez les plus petites données des données à tri ARR [2] ~ arr [n] et échangez-les avec R [2]; Et ainsi de suite, sélectionnez les plus petites données des données à tri ARR [i] ~ arr [n], et échangez-les avec r [i] jusqu'à ce que tout tri soit terminé.
c) Exemple : Array int [] arr = {5,2,8,4,9,1};
-------------------------------------------------------
Première commande: données originales: 528491
Données minimales 1, mettez 1 en premier, c'est-à-dire les positions d'interchange 1 et 5,
Résultat de tri: 128495
-------------------------------------------------------
Deuxième commande:
Les données à l'extérieur de 1 {28495} sont comparées, 2 est la plus petite,
Résultat de tri: 128495
-------------------------------------------------------
La troisième commande:
Des données autres que 1 et 2 sont comparées {8495}, 4 est minime, 8 et 4 sont échangés
Résultat de tri: 124895
-------------------------------------------------------
La quatrième commande:
D'autres données autres que 1, 2, 4 sont comparées {895}, 5 est minimum, 8 et 5 sont échangés
Résultat de tri: 124598
-------------------------------------------------------
La cinquième commande:
D'autres données autres que 1, 2, 4, 5 sont comparées, 8 est minime, 8 et 9 sont échangés
Résultat de tri: 124589
-------------------------------------------------------
Remarque: La méthode pour obtenir le plus petit nombre dans chaque commande: Pour que la boucle compare, définissez une troisième température variable. Tout d'abord, comparez les deux premiers nombres, mettez le plus petit nombre en température, puis utilisez la température pour comparer les données restantes. Si des données inférieures à la température apparaissent, utilisez-les au lieu des données d'origine en température. Pour plus de détails, se référant aux exemples de code ci-dessous, je pense que vous avez appris l'instruction FOR LOOP avant d'apprendre à trier. De cette façon, il sera particulièrement facile à comprendre ici.
Exemple de code:
// Sélectionnez SORT PUBLIC CLASS SELECTIONNTORT {public static void main (String [] args) {int [] arr = {1,3,2,45,65,33,12}; System.out.println ("Avant Exchange:"); pour (int num: arr) {System.out.print (num + ""); } // Sélectionnez l'optimisation du tri pour (int i = 0; i <arr.length - 1; i ++) {// trier le i-tth ordre int k = i; pour (int j = k + 1; j <arr.length; j ++) {// sélectionnez le plus petit enregistrement if (arr [j] <arr [k]) {k = j; // Notez l'emplacement de la valeur minimale trouvée jusqu'à présent}} // Après la fin de la boucle intérieure, c'est-à-dire, après avoir trouvé le nombre minimum de cette boucle, puis échange si (i! = K) {// échanger un [i] et a [k] int temp = arr [i]; arr [i] = arr [k]; arr [k] = temp; }} System.out.println (); System.out.println ("après swap:"); pour (int num: arr) {System.out.print (num + ""); }}}Capture d'écran du résultat en cours:
Sélectionnez la complexité temporelle du tri: le nombre de comparaisons de types de sélection simples n'a rien à voir avec le tri initial de la séquence. En supposant que la séquence à tri a des éléments n, le nombre de comparaisons sera toujours n (n-1) / 2. Le nombre de mouvements est lié au tri initial de la séquence. Lorsque la séquence est positive, le nombre de mouvements est le moins, ce qui est 0. Lorsque la séquence est inversement séquencée, les mouvements les plus élevés sont 3N (n-1) / 2.
Ainsi, en résumé, la complexité du temps du tri simple est O (N2).