Le tri rapide est largement utilisé comme algorithme de tri efficace. La méthode Arrays.sort du JDK de SUN utilise le tri rapide.
Quick Sort adopte l’idée classique de diviser pour mieux régner :
Diviser : sélectionnez un X primitif (généralement le premier élément du tableau) et divisez le tableau en deux parties via une opération de partitionnement : la moitié gauche est inférieure ou égale à X et la moitié droite est supérieure ou égale à X. .
Conquérir : les sous-tableaux gauche et droit appellent le processus Divide de manière récursive.
Combiner : le tri rapide est utilisé comme algorithme de tri sur place et ne nécessite aucune opération de fusion.
On peut voir que la partie essentielle du tri rapide est le processus de partitionnement. Voici un exemple pour expliquer en détail comment partitionner le tableau (image tirée de « Introduction aux algorithmes »).
Initialisation : Sélectionnez la primitive P=2, qui est le premier élément du tableau. i=1,j=i+1=2 (l'indice du tableau commence par 1)
Invariant de boucle : les éléments entre 2~i sont tous inférieurs ou égaux à P, et les éléments entre i+1~j sont tous supérieurs ou égaux à P.
Processus en boucle : j passe de 2 à n, examinez l'élément en position j, et s'il est supérieur ou égal à P, continuez la boucle. S'il est inférieur à P, permutez les éléments en position j (qui ne doivent pas apparaître dans la plage i+1~j) avec les éléments en position i+1 (toujours dans la plage i+1~j après l'échange), et en même temps, changez i+1 . Cela maintient les invariants de boucle (voir la description des invariants de boucle ci-dessus). Jusqu'à j=n, la dernière opération de boucle est terminée.
Il convient de noter qu'après avoir terminé la boucle, l'élément en position i doit être échangé avec le premier élément du tableau pour répondre aux exigences que nous avons d'abord définies (correspondant à la i-ème étape de la figure).
Les lecteurs attentifs peuvent penser à une autre méthode de partitionnement plus simple, c'est-à-dire retirer les primitives et les stocker dans un autre tableau de même taille. Lorsqu'ils rencontrent des éléments plus petits que les primitives, ils sont stockés dans la moitié gauche du tableau. éléments plus grands que les primitives, ils sont stockés dans la moitié gauche du tableau. La complexité de telles opérations est également linéaire, à savoir Theta(n). Mais la complexité spatiale est doublée. C’est aussi l’avantage d’un tri rapide en place.
Copiez le code comme suit :
classe publique QuickSort {
vide statique privé QuickSort (tableau int [], début int, fin int)
{
si (début <fin)
{
int key=array[start];//Initialiser et enregistrer les primitives
int i=start,j;//Initialiser i,j
pour(j=début+1;j<=fin;j++)
if(array[j]<key)//Si l'élément ici est inférieur à la primitive, échangez cet élément avec l'élément en i+1, et ajoutez 1 à i S'il est supérieur ou égal à la primitive, continuez. la boucle.
{
int temp=tableau[j];
tableau[j]=tableau[i+1];
tableau[i+1]=temp;
je++;
}
}
array[start]=array[i];//Échanger des éléments et des primitives en i
tableau[i]=clé;
QuickSort(array, start, i-1);//appel récursif
QuickSort(tableau, i+1, fin);
}
}
public static void main (String[] arguments)
{
int[] array=nouveau int[]{11,213,134,44,77,78,23,43};
Tri rapide (tableau, 0, tableau.longueur-1);
pour(int i=0;i<array.length;i++)
{
System.out.println((i+1)+"th:"+array[i]);
}
}
}