Compréhension approfondie de l'algorithme de tri par insertion et de ses principes d'implémentation en Java

Compréhension approfondie de l'algorithme de tri par insertion et de son principe de mise en œuvre en Java

Le tri par insertion est un algorithme de tri simple mais couramment utilisé, et son principe de mise en œuvre est également relativement simple. Cet article approfondira l'algorithme de tri par insertion et ses principes de mise en œuvre en Java, et joindra des exemples de code spécifiques.

1. L'idée de l'algorithme de tri par insertion
L'idée du tri par insertion est d'insérer un élément à trier dans une position appropriée dans une séquence partielle déjà ordonnée, divisant ainsi la séquence en parties triées et non triées. Au cours du processus de tri, en comparant et en déplaçant constamment les positions des éléments, une séquence complètement ordonnée est finalement obtenue.

2. Étapes spécifiques de l'algorithme de tri par insertion
Les étapes spécifiques de l'algorithme de tri par insertion peuvent être divisées en les étapes suivantes :

1. Partez du premier élément et traitez-le comme une séquence triée.
2. Sortez l'élément suivant, parcourez d'arrière en avant dans la séquence triée et trouvez la position d'insertion appropriée.
3. Insérez l'élément dans la position appropriée dans la séquence triée.
4. Répétez les étapes 2 et 3 jusqu'à ce que tous les éléments soient insérés dans leurs positions appropriées.

3. Code d'implémentation de l'algorithme de tri par insertion
Ce qui suit est un exemple de code d'implémentation de l'algorithme de tri par insertion en 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;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {9, 5, 1, 3, 8, 4, 7, 2, 6};
        insertionSort(arr);
        System.out.println("排序结果：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Dans le code ci-dessus, insertionSort方法使用插入排序算法对数组进行排序。在每一次遍历中，将当前元素存储为key，然后将key与已排序序列中的元素逐个比较并移动位置，直到找到合适的插入位置。最后，将key est inséré dans la bonne position.

4. Complexité temporelle et complexité spatiale du tri par insertion
La complexité temporelle du tri par insertion est O(n^2), où n est la longueur de la séquence à trier. Dans le pire des cas, où la séquence est dans l’ordre inverse, n(n-1)/2 opérations de comparaison et de déplacement sont nécessaires. Mais dans des circonstances moyennes, le tri par insertion fonctionne bien.

La complexité spatiale du tri par insertion est O(1) car il ne nécessite qu'un niveau constant d'espace supplémentaire pour stocker les variables temporaires.

5. Résumé
Le tri par insertion est un algorithme de tri simple mais couramment utilisé. Le tri est obtenu en insérant un élément à trier dans une position appropriée dans la séquence triée. Son principe de mise en œuvre est relativement simple et adapté au tri de données à petite échelle. Une compréhension et une pratique approfondies du tri par insertion peuvent nous aider à mieux comprendre les concepts fondamentaux des algorithmes et des structures de données.

Ce qui précède est une compréhension approfondie de l'algorithme de tri par insertion et de ses principes de mise en œuvre en Java et une introduction à des exemples de code spécifiques. J'espère que cela t'aides!

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!