Comment implémenter un algorithme de tri par insertion en Java ?

1. Idée de base

La description de l'algorithme de tri par insertion (Insertion-Sort) est un algorithme de tri simple et intuitif. Il fonctionne en construisant une séquence ordonnée. Pour les données non triées, il analyse d'arrière en avant dans la séquence triée pour trouver la position correspondante et l'insérer.

2. Analyse de l'algorithme

1. Description de l'algorithme

De manière générale, le tri par insertion est implémenté sur le tableau en utilisant sur place. L'algorithme spécifique est décrit comme suit :

• Commencez par le premier élément, qui peut être considéré comme ayant été trié ;

• Retirez l'élément suivant et numérisez d'arrière en avant dans la séquence d'éléments triés ;

Si l'élément (trié) est supérieur au nouvel élément, déplacez l'élément à la position suivante
Répétez l'étape 3 jusqu'à ce que vous trouviez la position où l'élément trié est inférieur ou égal au nouvel élément ;

• Insérez le nouvel élément Après avoir atteint la position

• Répétez les étapes 2 à 5 ;

• 2. Analyse du processus

(1), marquez le premier élément (1) comme trié.

(2), extraire le premier élément non trié (28).

(3). Trouvez l'endroit où l'élément extrait est inséré ; comparez avec l'élément trié 1.

(4), 1 > 28 n'est pas vrai (Faux), insérez un élément à la position existante.

(5), découvrez où insérer les éléments extraits ; comparez avec les éléments triés 28.

(6), 28 > 3 est établi (Vrai), puis l'élément actuellement trié ({val1}) sera déplacé d'1 espace vers la droite.

(7), découvrez où insérer les éléments extraits ; comparez avec l'élément trié 1.

(8), 1 > 3 n'est pas vrai (Faux), insérez un élément à la position existante.

(9), et ainsi de suite

Trois implémentation d'algorithme

package com.algorithm.tenSortingAlgorithm;

import java.util.Arrays;

public class InsertionSort {
    private static void insertionSort(int[] arr) {
        int preIndex, current;
        for (int i = 1; i < arr.length; i++) {
            preIndex = i - 1;
            current = arr[i];
            while (preIndex >= 0 && arr[preIndex] > current) {
                arr[preIndex + 1] = arr[preIndex];
                preIndex--;
            }
            arr[preIndex + 1] = current;
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,28,3,21,11,7,6,18};
        insertionSort(arr);
        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!