Techniques d'implémentation et d'optimisation des performances de l'algorithme de tri par sélection Java

Techniques complètes d'implémentation et d'optimisation du code de tri de sélection Java

Selection Sort est un algorithme de tri simple et intuitif Son idée de base est de trouver le plus petit (ou le plus grand) élément dans un tableau non trié et de le placer à la fin. du tableau trié. Répétez cette étape jusqu'à ce que l'ensemble du tableau soit trié. Ce qui suit est une description détaillée de l'implémentation complète du tri par sélection en Java et des techniques d'optimisation.

Implémentation de base du tri par sélection :

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            int minIndex = i;
            for (int j = i+1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("排序后的数组：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Dans le code ci-dessus, nous définissons d'abord la méthode principale de tri par sélection selectionSort(int[] arr)。在主方法中，我们先计算数组的长度，然后通过两个嵌套的循环来查找未排序部分中的最小元素，并将其与当前位置的元素进行交换。重复这个步骤直到整个数组排序完成。最后，在main方法中，我们定义了一个示例数组，并调用了selectionSort méthode de tri.

La complexité temporelle du tri par sélection est O(n^2), ce qui signifie qu'à mesure que le nombre d'éléments augmente, le temps requis pour le tri augmentera quadratiquement. Cependant, nous pouvons utiliser certaines techniques pour améliorer l’efficacité du tri par sélection.

Astuce d'optimisation 1 : Réduisez le nombre d'opérations d'échange

À chaque tour de tri par sélection, nous trouverons le plus petit élément de la pièce non triée et l'échangerons avec l'élément à la position actuelle. Bien que cela soit nécessaire, cela peut avoir un impact sur les performances si chaque swap nécessite trois affectations. On peut réduire le nombre d'échanges en enregistrant directement la valeur d'index du plus petit élément puis en effectuant une seule opération d'affectation. Le code modifié ressemble à ceci :

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            int minIndex = i;
            for (int j = i+1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("排序后的数组：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Astuce d'optimisation 2 : Ajouter un jugement pour vérifier la partie triée

A chaque tour, on parcourt la partie non triée pour trouver le plus petit élément. Cependant, si au cours du processus de parcours, il s'avère que le plus grand élément de la partie triée est plus petit que le plus petit élément de la partie non triée, alors le tri est terminé et nous pouvons terminer le processus de tri plus tôt. Le code modifié est le suivant :

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            int minIndex = i;
            boolean sorted = true;
            for (int j = i+1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
                if (arr[j] < arr[j-1]) {
                    sorted = false;
                }
            }
            if (minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
            if (sorted) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("排序后的数组：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Grâce aux techniques d'optimisation ci-dessus, nous pouvons améliorer l'efficacité d'exécution du tri par sélection.

Résumé :

Le tri par sélection est un algorithme de tri simple mais moins efficace. L'efficacité du tri par sélection peut être améliorée en réduisant le nombre d'opérations d'échange et en ajoutant un jugement sur la partie triée. Cependant, bien que la complexité temporelle du tri par sélection soit O(n^2), il s'agit toujours d'un algorithme de tri efficace dans certains scénarios spécifiques.

J'espère que cet article pourra vous aider à comprendre et à mettre en œuvre le tri par sélection, et à améliorer l'efficacité de l'algorithme grâce à certaines techniques d'optimisation.

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!