Quelle est l'idée d'implémenter un algorithme de tri rapide en Java

1. Qu'est-ce que l'algorithme de tri rapide

En fait, le tri rapide est une amélioration du tri à bulles ?

2. L'idée d'un algorithme de tri rapide

Divisez les données à trier en deux parties indépendantes grâce à un seul tri, et toutes les données d'une partie sont supérieures à toutes les données de l'autre partie doivent être petites, puis utilisez cette méthode pour trier rapidement les deux parties des données respectivement. L'ensemble du processus de tri peut être effectué de manière récursive, de sorte que l'ensemble des données devienne une séquence ordonnée.

(Tutoriel vidéo recommandé : Tutoriel vidéo Java )

3. Idées de mise en œuvre

(1) Prenez le premier mot-clé K 1 comme mots de contrôle. , divisez [K 1 ,K 2 ,…,K n ] en deux sous-zones, de sorte que tous les mots-clés de la zone de gauche soient inférieurs ou égaux à K 1 , tous les mots-clés de la zone de droite soient supérieurs ou égaux à K 1, et enfin le mot de contrôle est situé au milieu des deux sous-zones proprement dites. Les données de la sous-zone sont toujours dans un état désordonné. ;

(2) Traitez la zone gauche dans son ensemble et utilisez les étapes de (1) pour la traiter, et effectuez le même traitement sur la zone droite. (c'est-à-dire récursivité)

(3) Répétez les étapes (1) et (2) jusqu'à ce que la zone de gauche soit traitée.

4. Code d'implémentation

static void quicksort(int n[], int left, int right) {
        int dp;
        if (left < right) {
            dp = partition(n, left, right);
            quicksort(n, left, dp - 1);
            quicksort(n, dp + 1, right);
        }
    }
 
    static int partition(int n[], int left, int right) {
        int pivot = n[left];
        while (left < right) {
            while (left < right && n[right] >= pivot)
                right--;
            if (left < right)
                n[left++] = n[right];
            while (left < right && n[left] <= pivot)
                left++;
            if (left < right)
                n[right--] = n[left];
        }
        n[left] = pivot;
        return left;
    }

Tutoriel recommandé : Programme d'entrée Java

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!