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 :
Étape 1 : Sélectionnez l'élément pivot
On choisit le dernier élément comme pivot :
É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 :
Si un élément plus petit que le pivot est trouvé, on l'échange avec le deuxième pointeur :
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é :
Continuez ce processus jusqu'à atteindre la fin du tableau :
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 :
É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].
Continuez à diviser les sous-tableaux de cette manière jusqu'à ce que chaque sous-tableau ne contienne qu'un seul élément :
À ce stade, le tableau est trié.
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éthodequickSort
: 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!

Cet article analyse les quatre premiers cadres JavaScript (React, Angular, Vue, Svelte) en 2025, en comparant leurs performances, leur évolutivité et leurs perspectives d'avenir. Alors que tous restent dominants en raison de fortes communautés et écosystèmes, leur populaire relatif

L'article examine la mise en œuvre de la mise en cache à plusieurs niveaux en Java à l'aide de la caféine et du cache de goyave pour améliorer les performances de l'application. Il couvre les avantages de configuration, d'intégration et de performance, ainsi que la gestion de la politique de configuration et d'expulsion le meilleur PRA

Node.js 20 améliore considérablement les performances via des améliorations du moteur V8, notamment la collecte des ordures et les E / S plus rapides. Les nouvelles fonctionnalités incluent une meilleure prise en charge de Webassembly et des outils de débogage raffinés, augmentant la productivité des développeurs et la vitesse d'application.

Le chargement de classe de Java implique le chargement, la liaison et l'initialisation des classes à l'aide d'un système hiérarchique avec Bootstrap, Extension et Application Classloaders. Le modèle de délégation parent garantit que les classes de base sont chargées en premier, affectant la classe de classe personnalisée LOA

Cet article aborde la vulnérabilité CVE-2022-1471 dans SnakeyAml, un défaut critique permettant l'exécution du code distant. Il détaille comment la mise à niveau des applications de démarrage de printemps vers SnakeyAml 1.33 ou ultérieurement atténue ce risque, en soulignant cette mise à jour de dépendance

Iceberg, un format de table ouverte pour les grands ensembles de données analytiques, améliore les performances et l'évolutivité du lac Data. Il aborde les limites du parquet / orc par le biais de la gestion interne des métadonnées, permettant une évolution efficace du schéma, un voyage dans le temps, un W simultanément

Cet article explore l'intégration de la programmation fonctionnelle dans Java à l'aide d'expressions Lambda, de flux API, de références de méthode et facultatif. Il met en évidence des avantages tels que l'amélioration de la lisibilité au code et de la maintenabilité grâce à la concision et à l'immuabilité

L'article discute de l'utilisation de Maven et Gradle pour la gestion de projet Java, la construction de l'automatisation et la résolution de dépendance, en comparant leurs approches et leurs stratégies d'optimisation.


Outils d'IA chauds

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

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

Undress AI Tool
Images de déshabillage gratuites

Clothoff.io
Dissolvant de vêtements AI

AI Hentai Generator
Générez AI Hentai gratuitement.

Article chaud

Outils chauds

MantisBT
Mantis est un outil Web de suivi des défauts facile à déployer, conçu pour faciliter le suivi des défauts des produits. Cela nécessite PHP, MySQL et un serveur Web. Découvrez nos services de démonstration et d'hébergement.

DVWA
Damn Vulnerable Web App (DVWA) est une application Web PHP/MySQL très vulnérable. Ses principaux objectifs sont d'aider les professionnels de la sécurité à tester leurs compétences et leurs outils dans un environnement juridique, d'aider les développeurs Web à mieux comprendre le processus de sécurisation des applications Web et d'aider les enseignants/étudiants à enseigner/apprendre dans un environnement de classe. Application Web sécurité. L'objectif de DVWA est de mettre en pratique certaines des vulnérabilités Web les plus courantes via une interface simple et directe, avec différents degrés de difficulté. Veuillez noter que ce logiciel

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

Adaptateur de serveur SAP NetWeaver pour Eclipse
Intégrez Eclipse au serveur d'applications SAP NetWeaver.

Dreamweaver Mac
Outils de développement Web visuel
