Une sorte d'amélioration du tri bouillonnant est que si la séquence d'enregistrement initiale est commandée ou essentiellement commandée par des mots clés, il dégénérera en tri bouillonnant. Le principe de la récursivité est utilisé et ses performances moyennes sont les meilleures parmi toutes les méthodes de tri du même ordre de grandeur O (n Longn). En termes de temps moyen, il est actuellement considéré comme la meilleure méthode de tri interne.
L'idée de base est la suivante: divisez les données à tri en deux parties indépendantes en triant le tri, et toutes les données sont en partie plus petites que toutes les données de l'autre partie, puis trier rapidement ces deux parties des données selon cette méthode .
Trois pointeurs: le premier pointeur est appelé un pointeur Pivotkey (pivot), le deuxième pointeur et le troisième pointeur sont respectivement pointeur gauche et pointeur droit, pointant la valeur la plus à gauche et la valeur la plus à droite. Le pointeur gauche et l'approche du pointeur droit des deux côtés au milieu en même temps. Pivot vers le haut de gamme.
Deux fonctions sont nécessaires:
① Fonction récursive publique statique void Quicksort (int [] n, int gauche, int droit)
② Fonction du segment (une fonction de tri rapide) Public static int partition (int [] n, int gauche, int droit)
Code source Java (exécuter avec succès):
La copie de code est la suivante:
Package TestSortalgorithme;
classe publique Quicksort {
public static void main (String [] args) {
int [] array = {49,38,65,97,76,13,27};
Quicksort (Array, 0, Array.Length - 1);
for (int i = 0; i <array.length; i ++) {
System.out.println (array [i]);
}
}
/ * Écrivez d'abord l'algorithme comme prototype de données selon le tableau, puis écrivez l'algorithme d'évolutivité. Array {49,38,65,97,76,13,27}
* * /
public static void Quicksort (int [] n, int gauche, int droit) {
int pivot;
if (gauche <droite) {
// pivot comme pivot, l'élément plus petit est à gauche et l'élément plus grand est à droite
pivot = partition (n, gauche, droite);
// Appelle rapidement le tri rapide sur les tableaux gauche et droit jusqu'à ce que la commande soit complètement correcte
Quicksort (n, gauche, pivot - 1);
Quicksort (n, pivot + 1, à droite);
}
}
Public static int partition (int [] n, int Left, int droit) {
int pivotkey = n [gauche];
// Le pivot ne changera jamais après avoir été sélectionné, et il finira par être au milieu, avec un petit avant et un grand dos
while (gauche <droite) {
while (gauche <droite && n [droite]> = pivotkey) - droite;
// Déplacez l'élément plus petit que le pivot vers le bas de gamme.
n [gauche] = n [droite];
while (gauche <droit && n [gauche] <= pivotkey) ++ gauche;
// Déplacez l'élément plus grand que le pivot vers le haut de gamme.
n [droite] = n [gauche];
}
// À gauche == à droite, terminer un voyage de tri rapide.
n [gauche] = pivotkey;
retour à gauche;
}
}