Principe et code d'implémentation Java Quicksort

QuickSort est un algorithme de tri plus utilisé et plus efficace et est souvent mentionné pendant le processus d'entrevue. Expliquons ses principes en détail et donnons une implémentation de la version Java.

Idée de tri rapide:

Deux pièces indépendantes sont divisées en triant le jeu d'éléments de données RN en un seul voyage. Une partie du mot-clé est plus petite que l'autre partie. Triez ensuite les mots clés des deux parties une par un jusqu'à ce qu'il n'y ait qu'un seul élément indépendant, et la collection d'éléments entière est en ordre.

Le processus de tri rapide - la méthode de creuser des trous et de remplir les nombres (c'est un nom très vivant), pour un élément set r [Low ... High], prenez d'abord un nombre (généralement r [bas]) comme référence et R [Low] réorganise tous les éléments comme la référence.

Tous ceux plus petits que r [bas] sont placés à l'avant, tous ceux plus grands que r [bas] sont placés à l'arrière, puis R [Low] est utilisé comme limite, et R [Low ... High] est divisé en deux sous-ensembles puis divisé. Jusqu'à bas> = haut.

Par exemple: le processus d'exécution d'un tri rapide de r = {37, 40, 38, 42, 461, 5, 7, 9, 12} est le suivant (Remarque: Le tableau des éléments suivant décrit ci-dessous commence à partir de 0):

Commencez à sélectionner la base de base = 37, le tableau ci-dessous est faible = 0, haut = 8, à partir de haut = 8, si r [8] <base, écrivez la teneur en position élevée en r [bas], puis élevé La position est vide, faible = faible +1;

Commencez à sonder à partir de bas, puisque faible = 1, r [bas]> base, écrivez r [bas] à r [haut], élevé = élevé -1;

Low <High est détecté, donc le premier tri rapide doit encore continuer:

À ce moment bas = 1, haut = 7, car r [high] <base, r [high] est écrit en r [bas], faible = faible + 1;

Démarrer la détection de bas, bas = 2, r [bas]> base, donc r [bas] est écrit à r [high], high = high-1;

Continuer à détecter faible

À ce moment bas = 2, élevé = 6, de même, r [haut] <base, écrivez r [haut] à r [bas], bas = bas + 1;

Continuez à détecter à partir de bas, bas = 3, élevé = 6, r [bas]> base, écrivez r [bas] à r [haut], élevé = élevé-1;

Continuer à détecter que le faible est inférieur à

À ce moment bas = 3, élevé = 5, de même, r [haut] <base, écrivez r [high] en r [bas], faible = faible +1;

Continuez à sonder à partir de bas, bas = 4, élevé = 5, car r [bas]> base, écrivez r [bas] en r [haut], élevé = élevé -1;

À ce moment, Low == High == 4 est détecté; cette position est l'emplacement où la base est située et la base est écrite à cette position.

Ensuite, faites un tri rapide des sous-séquences RS1 = {12,9,7,5} et rs2 = {461,42,38,40} jusqu'à ce qu'il n'y ait qu'un seul élément dans RSI, ou aucun élément.

(Remarque: Dans le formulaire ci-dessus, vous pouvez voir qu'il existe des données en double dans le tri (pas de données en double dans les données d'origine). En effet Bloquez à un moment précis.

Implémentation rapide de Java:

La copie de code est la suivante:

Isempty booléen statique privé (int [] n) {

retour n == null || n.length == 0;

}

// /////////////////////////////////////////////////////////////////////////// / ///

/ **

* Idée d'algorithme de tri rapide - Méthode pour creuser des trous et le remplissage:

*

* @param n tableau à tri

* /

public static void Quicksort (int [] n) {

if (isEempty (n))

retour;

Quicksort (n, 0, n.length - 1);

}

public static void Quicksort (int [] n, int l, int h) {

if (isEempty (n))

retour;

if (l <h) {

int pivot = partition (n, l, h);

Quicksort (N, L, Pivot - 1);

Quicksort (n, pivot + 1, h);

}

}

partition statique privée intatique (int [] n, int start, int fin) {

int tmp = n [start];

while (start <end) {

while (n [fin]> = tmp && start <end)

fin--;

if (start <end) {

n [start ++] = n [fin];

}

while (n [start] <tmp && start <end)

start ++;

if (start <end) {

n [end--] = n [start];

}

}

n [start] = tmp;

retour de retour;

}

Il y a une fonction comme celle-ci dans le code:

La copie de code est la suivante:

public static void Quicksortswap (int [] n, int l, int h)

Cette fonction peut être implémentée pour trier les éléments de données dans l'ensemble des éléments entre les positions L et H spécifiques.

C’est tout pour le tri rapide.