Explication détaillée de l'algorithme de tri par insertion implémenté en Java

Explication détaillée de la méthode d'implémentation de l'algorithme de tri par insertion Java

Le tri par insertion est un algorithme de tri simple et intuitif. Son principe est de diviser la séquence à trier en parties triées et non triées, et à chaque fois elle n'est pas triée. Prenez un élément et insérez-le dans la position triée appropriée. La méthode de mise en œuvre de l'algorithme de tri par insertion est relativement simple. La méthode de mise en œuvre spécifique sera présentée en détail ci-dessous et des exemples de code correspondants seront donnés.

1. Idée d'algorithme
   Supposons que vous souhaitiez trier un tableau d'entiers arr par ordre croissant. Initialement, arr[0] est considéré comme la partie triée et les éléments restants sont considérés comme la partie non triée. Sur cette base, si l'élément actuel à insérer est arr[i] (i commence à partir de 1), alors trouvez la position j où arr[i] doit être inséré à partir de la partie triée arr[0:i-1], et puis arr[i] est inséré dans la position j, et tous les éléments de arr[j:i-1] sont déplacés vers l'arrière d'une position dans l'ordre.
2. Implémentation du code
   Ce qui suit est un exemple de code pour implémenter l'algorithme de tri par insertion en langage Java :

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; ++i) {
            int key = arr[i];
            int j = i - 1;

            // 将已排序的元素依次向后移动，直到找到arr[i]应该插入的位置
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 3, 1};
        insertionSort(arr);
        System.out.println("排序后的数组：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

3. Analyse de l'algorithme
   La complexité temporelle de l'algorithme de tri par insertion est O(n^2), où n est le nombre des éléments à trier. Dans le meilleur des cas, c'est-à-dire que le tableau à trier est déjà trié, la complexité temporelle du tri par insertion est O(n). Dans le pire des cas, le tableau à trier est dans l'ordre inverse et la complexité temporelle du tri par insertion est O(n^2). Le tri par insertion est un algorithme de tri stable car les positions relatives d'éléments égaux ne changent pas avant et après le tri.

En résumé, cet article présente en détail la méthode d'implémentation de l'algorithme de tri par insertion Java et donne des exemples de code correspondants. Le tri par insertion est un algorithme de tri simple et intuitif adapté aux tableaux à petite échelle ou aux tableaux essentiellement ordonnés. Dans les applications pratiques, le tri par insertion peut être remplacé par d'autres algorithmes de tri plus efficaces, mais comprendre les principes et les méthodes de mise en œuvre du tri par insertion est très bénéfique pour apprendre d'autres algorithmes de tri.

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!