Quick Sort est une amélioration du tri à bulles basée sur l'idée binaire. L'idée principale est d'établir une base, de placer les nombres plus petits que la base à gauche de la base et de placer les nombres plus grands que la base à droite de la base, puis de trier davantage les deux parties des nombres pour obtenir tri du tableau.
Son avantage est une efficacité élevée et la complexité temporelle moyenne est O(nlogn). Comme son nom l'indique, le tri rapide est l'algorithme de tri le plus rapide et consomme peu de ressources. Dans le meilleur des cas, la complexité spatiale est O(logn). est divisé également à chaque fois. Dans le cas des tableaux, le code est relativement simple.
Son inconvénient est qu'elle est instable Lorsque la séquence initiale est ordonnée ou fondamentalement ordonnée, la complexité temporelle tombe à O(n^2).
Par exemple:
publicclassMain{//Méthode d'implémentation de ligne rapide publicstaticvoidquickRow(int[]array,intlow,inthigh){inti,j,pivot;//Condition de fin if(low>=high){return;}i=low;j=high;/ /Le nœud sélectionné, le premier numéro du tableau sélectionné ici est utilisé comme nœud pivot=array[low];while(i<j){//Recherchez un nombre plus petit que le nœud de droite à gauche. de la boucle, soit il est trouvé, soit i =jwhile(array[j]>=pivot&&i<j){j--;}//Recherche un nombre plus grand que le nœud de gauche à droite. , soit il est trouvé, soit i=jwhile(array[i]<=pivot&&i <j){i++;}//Si des instructions i!=j sont trouvées, échangez les deux nombres if(i<j){inttemp=array [i];array[i]=array[j];array [j]=temp;}}//i==j Un cycle se termine, le nombre de nœuds d'échange et le nombre de points de rencontre array[low]=array [i];array[i]=pivot;//array "divided" "Deux moitiés", puis répétez l'opération ci-dessus quickRow(array,low,i-1);quickRow(array,i+1,high);} publicstaticvoidmain(String[]args){int[]array={6,17, 38,59,2,10};intlow=0,high=array.length-1;quickRow(array,low,high);for( inti:array){System.out.println(i);}}}Les résultats en cours d'exécution sont les suivants :
2610173859