Une compréhension simple du tri rapide

Partage de ressources de qualité

Guide d'apprentissage（Cliquez pour déverrouiller）	Positionnement des connaissances	Orientation de la population
🧡 PythonApplet de commande de repas Wechat en direct 🧡	Classe supérieure	Ce cours estpython flask+Une combinaison parfaite d'applets Wechat,De la construction du projet au déploiement de Tencent Cloud en ligne,Créer un système de commande de repas complet.
PythonQuantifier les transactions en direct	Niveau d'entrée	Les poignées vous permettent de créer une extension facile、Plus sûr、Un système d'échange quantitatif plus efficace

Description détaillée

Le tri rapide divise la séquence à organiser en deux parties distinctes par un tri,Les mots - clés d'une partie de la séquence sont plus petits que ceux de l'autre partie de la séquence,Vous pouvez continuer à trier les deux parties de la séquence séparément,Afin d'obtenir l'ordre de toute la séquence.

Les étapes détaillées pour un tri rapide sont les suivantes：

1. Choisissez un élément de la séquence,Appelé “Niveau de référence”（pivot）;
2. Réorganiser la séquence,Tous les éléments inférieurs à la valeur de référence sont placés devant la référence,Tous les éléments supérieurs à la valeur de référence sont placés derrière la référence（Le même nombre peut être de chaque côté）.Après la sortie de cette section,La référence est au milieu de la séquence.Ça s'appelle la partition（partition）Fonctionnement;
3. Récursivement（recursive） Trier les sous - séquences inférieures à l'élément de référence et les sous - séquences supérieures à l'élément de référence .

Diagramme d'algorithme

Résolution de problèmes

Comment choisir une valeur de référence pour un tri rapide ？

La première façon： Base de sélection de position fixe ; Avec toute la séquence en ordre ,Très inefficace.

La deuxième façon： Choisissez au hasard n'importe quel nombre de la séquence à organiser comme valeur de référence ; Lorsque la séquence tend à être ordonnée , Peut améliorer l'efficacité , Mais quand tout le nombre de séquences est égal , L'efficacité de l'alignement rapide aléatoire est encore très faible .

La troisième façon： Depuis le début de la section 、La queue、Au milieu,Prenez un nombre séparément,Puis comparez la taille,Prends ça. 3 La valeur médiane du nombre comme valeur de référence ; Cette approche résout de nombreux problèmes particuliers , Mais pour les séquences avec beaucoup de valeurs répétées , L'effet n'est toujours pas bon .

Quelles sont les bonnes façons d'optimiser le tri rapide ？

Tout d'abord,, Sélection raisonnable des valeurs de référence , Remplacer la valeur de référence de sélection de position fixe par la méthode de la médiane en trois points , De nombreuses situations particulières peuvent être résolues , Réaliser une partition plus rapide .

Deuxièmement,,Lorsque la longueur de la séquence à trier est divisée en une certaine taille,Tri par insertion. Lorsque la longueur de la séquence à trier est faible ou tend essentiellement à être ordonnée , Le tri des Inserts est plus efficace .

Après tri, Vous pouvez mettre un nombre égal à la valeur de référence ensemble , Ces chiffres peuvent être ignorés lors de la prochaine scission . Très utile pour résoudre les situations où les données sont en double .

Dans la mise en œuvre, Le tri rapide de l'implémentation récursive a deux opérations récursives à la fin de la fonction , Vous pouvez utiliser l'optimisation récursive de la queue （En termes simples, C'est la queue qui s'appelle elle - même ）.

Mise en œuvre du Code

|  | package cn.fatedeity.algorithm.sort; |
|  |  |
|  | import java.util.Random; |
|  |  |
|  | /** |
|  |  * Algorithme de tri rapide |
|  |  */ |
|  | public class QuickSort { |
|  | private static void swap(int[] numbers, int src, int target) { |
|  | int temp = numbers[src]; |
|  |  numbers[src] = numbers[target]; |
|  |  numbers[target] = temp; |
|  |  } |
|  |  |
|  | private static int[] sort(int[] numbers, int low, int high) { |
|  | if (low > high) { |
|  | return numbers; |
|  |  } |
|  | //  Le nombre aléatoire prend la valeur de référence  |
|  | Random random = new Random(); |
|  | int pivotIndex = random.nextInt(low, high + 1); |
|  | int pivot = numbers[pivotIndex]; |
|  |  swap(numbers, pivotIndex, low); |
|  |  |
|  | int mid = low + 1; |
|  | for (int i = low + 1; i <= high; i++) { |
|  | if (numbers[i] < pivot) { |
|  |  swap(numbers, i, mid); |
|  |  mid++; |
|  |  } |
|  |  } |
|  |  swap(numbers, low, --mid); |
|  |  sort(numbers, low, mid - 1); |
|  |  sort(numbers, mid + 1, high); |
|  | return numbers; |
|  |  } |
|  |  |
|  | public static int[] sort(int[] numbers) { |
|  | return sort(numbers, 0, numbers.length - 1); |
|  |  } |
|  | } |