recherche
MaisonJavajavaDidacticielComprendre l'algorithme de tri rapide (avec des exemples en Java)

Explication détaillée de l'algorithme QuickSort : un outil de tri efficace

QuickSort est un algorithme de tri efficace basé sur la stratégie diviser pour régner. La méthode diviser pour régner décompose le problème en sous-problèmes plus petits, résout ces sous-problèmes séparément, puis combine les solutions des sous-problèmes pour obtenir la solution finale. Dans le tri rapide, un tableau est divisé en sélectionnant un élément de partition, qui détermine le point de division du tableau. Avant le partitionnement, la position de l'élément de partitionnement est réorganisée de manière à ce qu'il soit avant l'élément qui est plus grand que lui et après l'élément qui est plus petit que lui. Les sous-tableaux gauche et droit seront divisés de manière récursive de cette manière jusqu'à ce que chaque sous-tableau ne contienne qu'un seul élément, auquel cas le tableau est trié.

Fonctionnement du tri rapide

Trions le tableau suivant par ordre croissant à titre d'exemple :

Understanding Quick Sort Algorithm (with Examples in Java)

Étape 1 : Sélectionnez l'élément pivot

On choisit le dernier élément comme pivot :

Understanding Quick Sort Algorithm (with Examples in Java)

Étape 2 : Réorganiser les éléments de pivot

Nous plaçons l'élément pivot avant les éléments qui sont plus grands que lui et après les éléments qui sont plus petits que lui. Pour ce faire, nous allons parcourir le tableau et comparer le pivot à chaque élément qui le précède. Si un élément plus grand que le pivot est trouvé, nous créons un deuxième pointeur pour celui-ci :

Understanding Quick Sort Algorithm (with Examples in Java)

Si un élément plus petit que le pivot est trouvé, on l'échange avec le deuxième pointeur :

Understanding Quick Sort Algorithm (with Examples in Java)

Répétez ce processus, en définissant l'élément suivant plus grand que le pivot sur le deuxième pointeur, en échangeant si un élément plus petit que le pivot est trouvé :

Understanding Quick Sort Algorithm (with Examples in Java)

Continuez ce processus jusqu'à atteindre la fin du tableau :

Understanding Quick Sort Algorithm (with Examples in Java)

Après avoir terminé la comparaison des éléments, l'élément plus petit que le pivot a été déplacé vers la droite, puis on échange le pivot avec le deuxième pointeur :

Understanding Quick Sort Algorithm (with Examples in Java)

Étape 3 : Divisez le tableau

Divisez le tableau en fonction de l'index de partition. Si nous représentons le tableau comme arr[start..end], alors en divisant le tableau par partition, nous pouvons obtenir le sous-tableau gauche arr[start..partitionIndex-1] et le sous-tableau droit arr[partitionIndex 1..end].

Understanding Quick Sort Algorithm (with Examples in Java)

Continuez à diviser les sous-tableaux de cette manière jusqu'à ce que chaque sous-tableau ne contienne qu'un seul élément :

Understanding Quick Sort Algorithm (with Examples in Java)

À ce stade, le tableau est trié.

Understanding Quick Sort Algorithm (with Examples in Java)

Implémentation du code de tri rapide

import java.util.Arrays;

public class QuickSortTest {
    public static void main(String[] args){
        int[] arr = {8, 6, 2, 3, 9, 4};
        System.out.println("未排序数组: " + Arrays.toString(arr));
        quickSort(arr, 0, arr.length-1);
        System.out.println("已排序数组: " + Arrays.toString(arr));
    }

    public static int partition(int[] arr, int start, int end){
        // 将最后一个元素设置为枢轴
        int pivot = arr[end];
        // 创建指向下一个较大元素的指针
        int secondPointer = start-1;

        // 将小于枢轴的元素移动到枢轴左侧
        for (int i = start; i < end; i++){
            if (arr[i] < pivot){
                secondPointer++;
                // 交换元素
                int temp = arr[secondPointer];
                arr[secondPointer] = arr[i];
                arr[i] = temp;
            }
        }
        // 将枢轴与第二个指针交换
        int temp = arr[secondPointer+1];
        arr[secondPointer+1] = arr[end];
        arr[end] = temp;
        // 返回分区索引
        return secondPointer+1;
    }

    public static void quickSort(int[] arr, int start, int end){
        if (start < end){
            // 找到分区索引
            int partitionIndex = partition(arr, start, end);
            // 递归调用快速排序
            quickSort(arr, start, partitionIndex-1);
            quickSort(arr, partitionIndex+1, end);
        }
    }
}

Interprétation du code

Méthode

quickSort : appelez d'abord la méthode partition pour diviser le tableau en deux sous-tableaux, puis appelez quickSort de manière récursive pour trier les sous-tableaux gauche et droit. Ce processus se poursuit jusqu'à ce que tous les sous-tableaux contiennent exactement un élément, auquel cas le tableau est trié.

partition Méthode : responsable de la division du tableau en deux sous-tableaux. Il définit d'abord le pivot et le pointeur sur l'élément le plus grand suivant, puis parcourt le tableau, déplaçant les éléments plus petits que le pivot vers la gauche. Après cela, il échange le pivot avec le deuxième pointeur et renvoie la position de la partition.

Exécutez le code ci-dessus, la console affichera ce qui suit :

Tableau non trié : [8, 6, 2, 3, 9, 4] Tableau trié : [2, 3, 4, 6, 8, 9]

Complexité temporelle

Meilleur des cas (O(n log n)) : Le meilleur des cas se produit lorsque le pivot divise le tableau en deux parties presque égales à chaque fois.

Cas moyen (O(n log n)) : Dans le cas moyen, le pivot divise le tableau en deux parties inégales, mais la profondeur de récursion et le nombre de comparaisons sont toujours proportionnels à n log n.

Pire des cas (O(n²)) : Le pire des cas se produit lorsque le pivot divise toujours le tableau en parties très inégales (par exemple, une partie n'a qu'un seul élément et l'autre a n-1 éléments). Cela peut se produire, par exemple, lors du tri d'un tableau dans l'ordre inverse et que le pivot est mal choisi.

Complexité spatiale (O(log n)) : le tri rapide est généralement implémenté sur place et ne nécessite pas de tableaux supplémentaires.

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!

Déclaration
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Y a-t-il des technologies émergentes qui menacent ou améliorent l'indépendance de la plate-forme de Java?Y a-t-il des technologies émergentes qui menacent ou améliorent l'indépendance de la plate-forme de Java?Apr 24, 2025 am 12:11 AM

Les technologies émergentes représentent à la fois des menaces et améliorent l'indépendance de la plate-forme de Java. 1) Les technologies de cloud computing et de contenerisation telles que Docker améliorent l'indépendance de la plate-forme de Java, mais doivent être optimisées pour s'adapter à différents environnements cloud. 2) WebAssembly compile le code Java via GRAALVM, prolongeant son indépendance de la plate-forme, mais il doit rivaliser avec d'autres langues pour les performances.

Quelles sont les différentes implémentations du JVM et fournissent-elles toutes le même niveau d'indépendance de la plate-forme?Quelles sont les différentes implémentations du JVM et fournissent-elles toutes le même niveau d'indépendance de la plate-forme?Apr 24, 2025 am 12:10 AM

Différentes implémentations JVM peuvent fournir une indépendance de la plate-forme, mais leurs performances sont légèrement différentes. 1. Oraclehotspot et OpenJDKJVM fonctionnent de manière similaire dans l'indépendance de la plate-forme, mais OpenJDK peut nécessiter une configuration supplémentaire. 2. IBMJ9JVM effectue une optimisation sur des systèmes d'exploitation spécifiques. 3. GRAALVM prend en charge plusieurs langues et nécessite une configuration supplémentaire. 4. AzulzingJVM nécessite des ajustements de plate-forme spécifiques.

Comment l'indépendance des plateformes réduit-elle les coûts et le temps de développement?Comment l'indépendance des plateformes réduit-elle les coûts et le temps de développement?Apr 24, 2025 am 12:08 AM

L'indépendance de la plate-forme réduit les coûts de développement et réduit le temps de développement en exécutant le même ensemble de code sur plusieurs systèmes d'exploitation. Plus précisément, il se manifeste comme suit: 1. Réduire le temps de développement, un seul ensemble de code est requis; 2. Réduire les coûts de maintenance et unifier le processus de test; 3. I itération rapide et collaboration d'équipe pour simplifier le processus de déploiement.

Comment l'indépendance de la plate-forme de Java facilite-t-elle la réutilisation du code?Comment l'indépendance de la plate-forme de Java facilite-t-elle la réutilisation du code?Apr 24, 2025 am 12:05 AM

Java'splatformIndependencyfaciliteraDereuseByAllowingBytecodetorunonanyplatformwithajvm.1) DevelopersCanwriteCodeonceForConsistentBehavioracrossplatforms.2) MaintenstarisoniSreducedAsCodoSoesSprojrit

Comment résoudre les problèmes spécifiques à la plate-forme dans une application Java?Comment résoudre les problèmes spécifiques à la plate-forme dans une application Java?Apr 24, 2025 am 12:04 AM

Pour résoudre les problèmes spécifiques à la plate-forme dans les applications Java, vous pouvez prendre les étapes suivantes: 1. Utilisez la classe système de Java pour afficher les propriétés du système pour comprendre l'environnement en cours d'exécution. 2. Utilisez la classe de fichiers ou le package java.nio.file pour traiter les chemins de fichier. 3. Chargez la bibliothèque locale en fonction des conditions du système d'exploitation. 4. Utilisez VisualVM ou JProfiler pour optimiser les performances de plate-forme multipliée. 5. Assurez-vous que l'environnement de test est cohérent avec l'environnement de production par la contenerisation Docker. 6. Utilisez des githubactions pour effectuer des tests automatisés sur plusieurs plates-formes. Ces méthodes aident à résoudre efficacement des problèmes spécifiques à la plate-forme dans les applications Java.

Comment le sous-système de chargeur de classe du JVM contribue-t-il à l'indépendance de la plate-forme?Comment le sous-système de chargeur de classe du JVM contribue-t-il à l'indépendance de la plate-forme?Apr 23, 2025 am 12:14 AM

Le chargeur de classe garantit la cohérence et la compatibilité des programmes Java sur différentes plates-formes via le format de fichier de classe unifié, le chargement dynamique, le modèle de délégation parent et les bytecode indépendants de la plate-forme et réalisent l'indépendance de la plate-forme.

Le compilateur Java produit-il un code spécifique à la plate-forme? Expliquer.Le compilateur Java produit-il un code spécifique à la plate-forme? Expliquer.Apr 23, 2025 am 12:09 AM

Le code généré par le compilateur Java est indépendant de la plate-forme, mais le code finalement exécuté est spécifique à la plate-forme. 1. Le code source Java est compilé en bytecode indépendant de la plate-forme. 2. Le JVM convertit le bytecode en code machine pour une plate-forme spécifique, garantissant un fonctionnement multiplateforme mais les performances peuvent être différentes.

Comment le JVM gère-t-il le multithreading sur différents systèmes d'exploitation?Comment le JVM gère-t-il le multithreading sur différents systèmes d'exploitation?Apr 23, 2025 am 12:07 AM

Le multithreading est important dans la programmation moderne car elle peut améliorer la réactivité du programme et l'utilisation des ressources et gérer des tâches simultanées complexes. JVM assure la cohérence et l'efficacité des multitheads sur différents systèmes d'exploitation grâce à la cartographie des filetages, au mécanisme de planification et au mécanisme de verrouillage de synchronisation.

See all articles

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

Video Face Swap

Video Face Swap

Échangez les visages dans n'importe quelle vidéo sans effort grâce à notre outil d'échange de visage AI entièrement gratuit !

Outils chauds

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

SublimeText3 version anglaise

SublimeText3 version anglaise

Recommandé : version Win, prend en charge les invites de code !

SublimeText3 Linux nouvelle version

SublimeText3 Linux nouvelle version

Dernière version de SublimeText3 Linux

Version Mac de WebStorm

Version Mac de WebStorm

Outils de développement JavaScript utiles

mPDF

mPDF

mPDF est une bibliothèque PHP qui peut générer des fichiers PDF à partir de HTML encodé en UTF-8. L'auteur original, Ian Back, a écrit mPDF pour générer des fichiers PDF « à la volée » depuis son site Web et gérer différentes langues. Il est plus lent et produit des fichiers plus volumineux lors de l'utilisation de polices Unicode que les scripts originaux comme HTML2FPDF, mais prend en charge les styles CSS, etc. et présente de nombreuses améliorations. Prend en charge presque toutes les langues, y compris RTL (arabe et hébreu) ​​et CJK (chinois, japonais et coréen). Prend en charge les éléments imbriqués au niveau du bloc (tels que P, DIV),