Maison  >  Article  >  Java  >  Comment écrire du code pour implémenter le tri à bulles et le tri par sélection en Java

Comment écrire du code pour implémenter le tri à bulles et le tri par sélection en Java

王林
王林avant
2023-04-20 12:55:12653parcourir

1. Tri à bulles

L'idée de base du tri à bulles est la suivante : traiter la séquence de tri

d'avant en arrière (en commençant par l'élément avec l'indice le plus petit), et comparer les valeurs des éléments adjacents. éléments dans l'ordre. Si l'ordre inverse est trouvé, les éléments sont échangés, de sorte que les éléments avec des valeurs plus grandes se déplacent progressivement de l'avant vers l'arrière, tout comme des bulles sous l'eau, s'élevant progressivement.

Car lors du processus de tri, chaque élément se rapproche constamment de sa propre position. Si aucun échange n'a été effectué lors d'une comparaison, cela signifie que la séquence est en ordre.

Illustration du processus d'algorithme de tri des bulles

Tableau original : 3, 9, -1, 10, 20

Premier passage de tri

(1) 3, 9, -1, 10 , 20 // Si les éléments adjacents sont dans l'ordre inverse, échangez-les


(2) 3, -1, 9, 10, 20


(3) 3, -1, 9, 10, 20


( 4) 3 , -1, 9, 10, 20

Deuxième tri

(1) -1, 3, 9, 10, 20 //Échange


(2) -1, 3, 9, 10 , 20


(3) -1, 3, 9, 10, 20

Le troisième tri

(1) -1, 3, 9, 10, 20


(2) -1 , 3, 9, 10, 20

La quatrième passe de tri

(1) -1, 3, 9, 10, 20

Résumé de la règle de tri des bulles

(1) A total de tableaux La taille de - 1 grande boucle


(2) Le nombre de fois de chaque tri diminue progressivement


(3) Si nous constatons qu'aucun échange ne se produit lors d'un certain voyage de tri, nous pouvons mettre fin à la bulle trier tôt. Voici le résultat de l'optimisation

import java.util.Arrays;
public class BubbleSort {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
        int arr[]= {3,9,-1,10,-2};
        //第i+1趟排序,将最大的数排在最后
        int temp=0;//临时变量
        for(int i=0;i<arr.length-1;i++) {//定义第几轮排序
       	 for(int j=0;j<arr.length-1-i;j++) {
       		 if(arr[j+1]<arr[j]) {
       		  temp=arr[j];
       		 arr[j]=arr[j+1];
       		 arr[j+1]=temp;
       		 }
       		 }
        System.out.println("输出第"+(i+1)+"趟排序的结果");
        System.out.println(Arrays.toString(arr));
        }
     
        }
	}
 :

Afficher les résultats du premier tri

[3, -1, 9, -2, 10]
Afficher les résultats du deuxième tri
[-1, 3, - 2 , 9, 10]
Afficher le résultat du troisième tri
[-1, -2, 3, 9, 10]
Afficher le résultat du quatrième tri
[-2, -1, 3, 9, 10]

2. Méthode de tri par sélection

Idée de tri :

Tableau original : 101, 34, 119, 1


Premier tour de tri : 1, 34, 119, 101


Deuxième tour de tri : 1, 34, 119, 101


Le troisième tour de tri : 1, 34, 101, 119

Instructions :

1. La taille totale du tri de sélection - 1 tour de tri

2. 1 tour de tri, une autre boucle, les règles (code) de la boucle

  • 2.1 Supposons d'abord que le nombre actuel est le plus petit nombre

  • 2.2 Comparez-le ensuite avec chaque nombre suivant, s'il s'avère qu'il y a est un nombre plus petit que le nombre actuel, redéterminez le nombre minimum et obtenez l'indice

  • 2.3 Lors du déplacement jusqu'à la fin du tableau, obtenez le nombre minimum et l'indice de ce tour

  • 2.4 Échange [continuer dans le code]

import java.util.Arrays;
public class QuickSort {
    public static void main(String[] args) {
       //int []arr={ 8,3,2,1,7,4,6,5};
       int [] arr={101,34,109,1};
       quicksort(arr);
    }
    public static void quicksort(int []arr){
        for(int j=0;j<arr.length-1;j++) {
            int minindex=j;//假定当前下标为最小值下标
            int minnumber=arr[j];//假定当前元素为最小值
            for (int i = 1+j; i < arr.length; i++) {
                if (arr[i] < minnumber) {//若假定最小值并不是最小的
                    minnumber = arr[i];//重置minnumber
                    minindex = i;//重置minindex
                }
            }
            //将最小值交换
            arr[minindex] = arr[j];
            arr[j] = minnumber;
            System.out.println("第"+(j+1)+"轮");
            System.out.println(Arrays.toString(arr));
        }
    }
}

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!

Déclaration:
Cet article est reproduit dans:. en cas de violation, veuillez contacter admin@php.cn Supprimer