Complexité temporelle
Moyenne: O (NLGN)
Pire des cas: O (n * n), se produit lorsque les données sont déjà dans l'état de tri.
1. Sélectionnez une valeur a [i] dans les données comme référence
2. Prendre un [i] comme référence, divisez les données en 2 parties: P1 et P2. Toutes les données de p1≤a [i], toutes les données de p2> a [i], et les données deviennent {{p1} {a [i]} {p2}}
3. Répétez les étapes ci-dessus avec P1 et P2 jusqu'à ce qu'une seule données soit laissée dans chaque partie.
4. Les données sont triées par ordre croissant
Exemple de base:
Données brutes:
{3, 9, 8, 5, 2, 1, 6} Étape 1: Sélectionnez les premières données: 3
Étape 2: Divisez les données en 2 parties, le côté gauche est ≤3 et le côté droit est supérieur à> 3:
{2,1} {3} {9,8,5,6} Étape 3: Répétez les étapes ci-dessus pour chaque partie jusqu'à ce qu'il ne reste plus que des données dans chaque partie:
{2,1} => {1} {2} {9, 8, 5, 6} => {8, 5, 6} {9} => {5, 6} {8} {9} => {5} {6} {8} {9} Étape 4: Les données sont triées dans l'ordre croissant:
{1} {2} {3} {5} {6} {8} {9}Les données du programme sont généralement stockées dans un tableau. En prenant un tableau de type INT à titre d'exemple, vous pouvez écrire les étapes ci-dessus dans un prototype de fonction Quicksort:
Quicksort (int début, int fin) {// begin est la valeur d'index des premières données du tableau, la fin de l'index est la valeur d'index des dernières données du tableau +1 // s'il n'y a que 1 données ou 0 données, le programme renvoie si (begin == end || begin == (end-1)) return; int p = dans [begin]; // p est les données de référence sélectionnées, sélectionnez les premières données int a = begin +1; // a comme la valeur d'index de la ligne de division des données en 2 parties int b = a; // b est la valeur d'index des données à comparer pour (; b <end; b ++) {// comparer les données du tableau avec les données de référence en séquence if (dans [b] <p) {// si les données de référence, les données, déplacent-la à gauche if (a == b) {a ++; continuer;} // si les données sont déjà à gauche, elles ne déplaceront pas int temp = dans [a]; // déplacer les données vers la gauche dans [a] = dans [b]; Dans [b] = temp; A ++; // Déplacez la ligne de division à droite}} dans [Begin] = dans [A-1]; // Whike la valeur de référence au milieu de 2 ensembles de données dans [A-1] = P; if (a-1> commencer) {// s'il y a des données sur la gauche, répétez les étapes ci-dessus Quicksort (Begin, a); } if (end-1> a) {// s'il y a des données à droite, répétez les étapes ci-dessus Quicksort (a, end); } retour; // s'il n'y a pas de données} Optimisation de l'algorithme
L'algorithme de tri rapide ci-dessus peut être considéré comme le tri rapide le plus basique car il ne prend en compte aucune donnée d'entrée. Cependant, il est facile de trouver les défauts de cet algorithme: c'est lorsque nos données d'entrée sont essentiellement commandées ou même complètement commandées, l'algorithme dégénère en tri à bulles, plus o (nn), mais o (n ^ 2).
La cause profonde est que dans notre implémentation de code, nous commençons uniquement à partir du premier tableau à la fois. Si nous utilisons le "trois têtes", c'est-à-dire les valeurs médianes de l'ARR [Low], Arr [High], ARR [(Low + High) / 2] comme enregistrement de pivot, les performances du tri rapide dans le pire des cas peuvent être considérablement améliorées. Cependant, nous ne pouvons toujours pas améliorer ses performances à O (n) dans le cas ordonné par tableau. Il existe également des moyens d'améliorer les performances temporelles du tri rapide dans le pire des cas à des degrés divers.
De plus, le tri rapide nécessite une pile récursive, qui n'est généralement pas très profonde et est au niveau du journal (n). Cependant, si la longueur des deux tableaux divisées à la fois est gravement déséquilibrée, dans le pire des cas, la profondeur de la pile augmentera à O (n). À l'heure actuelle, la complexité spatiale apportée par l'espace de pile ne peut pas être ignorée. Si les frais généraux de variables supplémentaires sont ajoutés, il peut même atteindre une complexité spatiale O (n ^ 2) terrifiante ici. Par conséquent, la pire complexité spatiale du tri rapide n'est pas une valeur fixe et peut même ne pas être au même niveau.
Pour résoudre ce problème, nous pouvons comparer les longueurs des extrémités après chaque division et trier d'abord les séquences courtes (le but est de mettre fin à ces piles d'abord pour libérer l'espace), ce qui peut réduire la profondeur maximale au niveau O (n).
Voici trois idées d'optimisation pour le tri rapide:
Pour les petits tableaux, le tri des insert peut être utilisé pour éviter les appels récursifs. Par exemple, lorsque (hi <= lo + m), vous pouvez aller pour insérer le tri.
Utilisez la médiane d'un sous-réseau pour trancher le tableau. Il en résulte un meilleur tranchage, mais au prix du calcul de la médiane.
Si le tableau contient un grand nombre d'éléments répétitifs, des tranches à trois voies peuvent être utilisées. Divisez le tableau en trois parties, correspondant à des éléments de tableau plus petits que, égaux à et supérieurs aux éléments de découpage respectivement. L'implémentation du code est la suivante:
private static void srie1 (int [] a, int lo, int hi) {if (hi <= lo) return; int lt = lo, i = lo + 1, gt = hi; int v = a [lo]; while (i <= gt) {if (a [i] <v) {swap (a, lt ++, i ++); } else if (a [i]> v) {swap (a, i, gt--); } else {i ++; } tri (a, lo, lt - 1); tri (a, gt + 1, hi); }}