Le tri rapide peut être très rapide lorsque vous entendez ce nom, mais le pire cas de sa complexité temporelle d'algorithme est le même que le tri de l'insertion. La raison pour laquelle il devient rapide est que son efficacité moyenne est plus rapide que le tri des tas. Besoin d'ouvrir un nouvel espace de stockage directement dans le tableau d'origine. L'idée de tri rapide est très simple, qui est de sélectionner un mot-clé K pour diviser le tableau d'origine en deux parties G1 et G2. Pour K. La méthode de tri dans le code est la description de l'instruction tout à l'heure. L'algorithme clé consiste à trouver l'emplacement de K et à diviser le tableau d'origine en deux parties. La méthode GetPlocation est au cœur du tri rapide. Son principe de mise en œuvre est un peu comme le tri des insert mais un peu comme. Chaque fois, l'élément à la position finale de la carte est utilisé comme mot clé. Et J est plus grand que le noyau. Avancez. Après avoir bouclé comme ceci, le début de la fin est séparé par la taille.
La copie de code est la suivante:
classe publique Quicksort {
public int getPlocation (int [] map, int start, int fin) {
int core = map [fin];
int i = start-1;
pour (int j = start; j <= end-1; j ++) {
if (map [j] <= core) {
i ++;
int cache = map [j];
map [j] = map [i];
map [i] = cache;
}
}
i ++;
map [end] = map [i];
map [i] = core;
retour i;
}
public void tri (int [] map, int start, int fin) {
if (start <end) {
int p = getPlocation (map, start, end);
tri (carte, démarrer, P-1);
tri (carte, p + 1, fin);
}
}
public static void main (String [] args) {
int [] map = new int [] {4,1,5,3,7,12,65,7};
Quicksort qs = new Quicksort ();
qs.sort (map, 0, map.length-1);
pour (int i = 0; i <map.length; i ++) {
System.out.println (map [i]);
}
}
}