Méthodes et principes d'écriture d'un algorithme de tri par insertion en Java

Étapes et idées de l'algorithme de tri par insertion

Le tri par insertion est un algorithme de tri simple et intuitif. Son idée de base est d'insérer les éléments à trier dans la position appropriée de la séquence triée.

Les étapes spécifiques sont les suivantes :

1. Tout d'abord, nous divisons le tableau en deux parties : la partie triée et la partie non triée. Initialement, il n'y a qu'un seul élément dans la partie triée, qui est le premier élément du tableau.
2. Nous retirons tour à tour un élément de la partie non triée, le comparons un par un avec les éléments de la partie triée et trouvons la position appropriée à insérer.
3. Pendant le processus de comparaison, nous déplaçons les éléments de la partie triée vers l'arrière pour faire de la place aux éléments insérés.
4. Enfin, on insère tous les éléments de la pièce non triée dans les positions appropriées de la pièce triée, et le tri est terminé.

Ce qui suit est un exemple de code pour écrire 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;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

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

    public static void printArray(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

Dans cet exemple de code, nous définissons une méthode insertionSort qui accepte un tableau d'entiers comme paramètre et effectue une fonction sur le tableau Effectuer un tri par insertion. Nous utilisons n pour représenter la longueur du tableau, et utilisons for pour parcourir les éléments de la partie non triée. Dans chaque parcours, nous enregistrons l'élément actuel arr[i] dans la variable key, puis parcourons la partie triée vers l'avant pour trouver la position appropriée pour insérer la clé . Pendant le processus de comparaison, nous reculons l'élément le plus grand d'une position pour faire de la place à key. Enfin, nous insérons la clé dans la bonne position et le tri est terminé. insertionSort方法，它接受一个整数数组作为参数，并对数组进行插入排序。我们用n表示数组的长度，并使用for循环遍历未排序部分的元素。在每一次遍历中，我们将当前元素arr[i]保存到key变量中，然后向前遍历已排序部分，找到合适的位置插入key。在比较的过程中，我们将较大的元素往后移动一位，为key腾出位置。最后，我们将key插入到正确的位置上，排序完成。

在main方法中，我们初始化一个整数数组arr，并调用insertionSort方法对数组进行排序。最后，我们调用printArray

Dans la méthode main, nous initialisons un tableau d'entiers arr et appelons la méthode insertionSort pour trier le tableau. Enfin, nous appelons la méthode printArray pour imprimer le tableau trié.

En exécutant le code ci-dessus, vous pouvez obtenir le résultat suivant :

原数组：
5 2 8 1 9 3 
排序后的数组：
1 2 3 5 8 9 

La complexité temporelle de l'algorithme de tri par insertion est O(n^2), où n est la longueur du tableau. Bien que l’algorithme de tri par insertion présente une complexité temporelle élevée, sa mise en œuvre est simple et adaptée au tri de tableaux à petite échelle. Dans le même temps, dans les applications pratiques, l'algorithme de tri par insertion présente également les caractéristiques de stabilité. 🎜

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!