Le tri rapide consiste à trouver un élément (à l'origine vous pouvez en trouver un) comme référence (pivot), puis partitionner le tableau afin que la valeur de l'élément à gauche de la référence ne soit pas supérieure à la valeur de référence, et la valeur de l'élément à droite de la référence n'est pas inférieur à la valeur de référence. Tri rapide récursivement, ajustez les autres éléments N-1 à la position correcte après le tri. Enfin, chaque élément est dans la position correcte après le tri et le tri est terminé. Par conséquent, l'algorithme central de l'algorithme de tri rapide est un opération de partitionnement, c'est-à-dire comment ajuster la position de la référence et ajuster la position finale de la référence de retour afin de diviser et de conquérir la récursivité.
L'algorithme pour le tri rapide est:
1) Réglez deux variables I et J, lorsque le tri commence: i = 0, j = n-1;
2) Utilisez le premier élément de tableau comme données de clés et attribuez-les à la clé, c'est-à-dire KEY = A [0];
3) Commencez de J pour rechercher en avant, c'est-à-dire commencer par derrière pour rechercher en avant (J--), trouver la première valeur A [j] plus petite que la clé et échanger un [j] et un [i];
4) Commencez à partir de I pour rechercher en arrière, c'est-à-dire commencer de l'avant en arrière (i ++), trouvez le premier un [i] plus grand que la clé et échangez un [i] et un [j];
5) Répétez les étapes 3 et 4 jusqu'à ce que i = j; (dans les étapes 3, 4, aucune valeur qui remplit les conditions n'est trouvée, c'est-à-dire quand un [j] en 3 n'est pas inférieur à la clé, et un [i] 4 n'est pas supérieur à la clé change les valeurs de j et i pour que j = j-1, i = i + 1 jusqu'à ce qu'elle soit trouvée. reste inchangé.
Permettez-moi de vous donner un exemple, cela peut ne pas être facile à comprendre. Supposons que la séquence à tri est
La copie de code est la suivante:
Package com.zc.ManyThread;
import java.util.random;
/ **
* Sort rapide
* @Author Administrator
*
* /
classe publique Qsort {
date int [];
public qsort (int [] date) {
this.date = date;
}
/ **
* Fonction d'échange
* @param a
* @param i
* @param j
* /
Échange de void privé (int a [], int i, int j) {
int t;
T = a [i];
a [i] = a [j];
a [j] = t;
}
/ *************************
* Trier la fonction
* @param a
* @param lo0
* @param hi0
* @retour
* /
int [] Quicksort (int a [], int lo0, int hi0) {// La méthode de division et de traitement consiste à diviser le tableau en un [lo0..q-1] et un [q + 1..hi0]
int lo = lo0;
int hi = hi0;
int mid;
if (hi0> lo0) {
mid = a [(hi0 + lo0) / 2];
while (lo <= hi) {
while ((lo <hi0) && (a [lo] <mid)) ++ lo;
while ((hi> lo0) && (a [hi]> mid)) --hi;
if (lo <= hi) {
échange (a, lo, hi);
++ lo;
--Salut;
}
}
if (lo0 <hi) {
Quicksort (A, LO0, HI);
}
if (lo <hi0) {
Quicksort (A, LO, HI0);
}
}
retourner a;
}
/ ******************
*
* Créer des données de tableau en double
********************** /
private static int [] CreateDate (int count) {
int [] data = new int [count];
for (int i = 0; i <data.length; i ++) {
data [i] = (int) (math.random () * count);
}
retourner les données;
}
/ **
* Pas de données de tableau en double
* @param count
* @retour
* /
private static int [] CreateDate1 (int count) {
int [] data = new int [count];
Random Rand = new Random ();
Boolean [] bool = new Boolean [100];
int num = 0;
pour (int i = 0; i <count; i ++) {
faire {
// Si le nombre généré est le même, continuez à boucler
num = rand.nextint (100);
} while (bool [num]);
bool [num] = true;
data [i] = num;
}
retourner les données;
}
/ ************ fonction principale ********************* /
public static void main (String [] args) {
Count int final = 10;
int [] data = CreateDate1 (count);
pour (int n: data) {
System.out.print (n + "/ t");
}
QSORT DATA1 = NOUVEAU QSORT (DATA);
System.out.println ();
int [] a = data1.quicksort (data, 0, count-1);
pour (int n: a) {
System.out.print (n + "/ t");
}
}
}
Les résultats sont les suivants:
Ce qui précède est tout le contenu décrit dans cet article.