Introduction aux principes du tri rapide
Le tri rapide est une mise à niveau du tri de bulles que nous avons appris auparavant. Ils appartiennent tous au tri des échanges, et ils utilisent tous une comparaison et un mouvement constants pour atteindre le tri. Le tri rapide est un algorithme de tri très efficace. Son implémentation augmente la distance entre la comparaison et le mouvement des enregistrements, et déplace les enregistrements avec des mots clés plus grands directement de l'avant vers l'arrière, et des enregistrements avec des mots clés plus petits directement de l'arrière à l'avant, réduisant ainsi le nombre total de comparaisons et de mouvements. Dans le même temps, l'idée de «diviser et conquérir» est adoptée pour diviser le grand en petit, et les petits en plus petits. Le principe est le suivant: pour un ensemble donné d'enregistrements, sélectionnez un élément de référence, généralement le premier élément ou le dernier élément est sélectionné, et à travers une analyse, la séquence à tri est divisée en deux parties, partie plus petite que l'élément de référence, et partie supérieure ou égale à l'élément de référence. À l'heure actuelle, l'élément de référence est dans la bonne position après son tri, puis les deux parties sont triées récursivement de la même manière jusqu'à ce que tous les enregistrements de la séquence soient commandés.
1. Le plus petit nombre de k
Entrez les nombres n pour trouver les plus petits nombres K, par exemple, entrez 4,5,1,6,2,7,3,8, et le plus petit nombre est de 1,2,3,4
Sur la base de O (n), ce problème peut être résolu en utilisant la fonction de partition. Si le numéro de Kth du tableau est ajusté en fonction du numéro de Kth, de sorte que tous les nombres plus petits que le Kth Numéro sont situés à gauche du tableau, et tous les nombres plus grands que le tableau Kth sont situés à droite du tableau. Après ajustement, les K nombres à gauche du tableau sont les plus petits nombres K, qui ne sont pas nécessairement commandés.
Importer java.util.scanner; public class Main {public static void main (String [] args) {scanner in = new scanner (system.in); int n = in.nextint (); int k = in.nextint (); int [] num = new int [n]; int [] out = new int [k]; for (int [] num = new int [n]; int [] out = new int [k]; for (int. i = 0; i <n; i ++) {num [i] = in.nextint ();} boolean b = getMink (n, num, k, out); if (b) {for (int i = 0; i <k; i ++) {System.out.print (out [i] + "");}}} public statian boolean getmink int uik, int [] poutputArray) {if (pinputArray == null || poutputArray == null || uik> uiinputnum || uiinputnum <= 0 || uik <= 0) {return false;} int start = 0; int end = uiInputNum-1; int index = partition (pinputArray, start, end); while (index! = uik-1) {if (index> uik-1) {// index est du côté droit de k-1 end = index-1; index = partition (pinputArray, start, end);} else {start = index + 1; index = partition (pinputArray, start, end);}} pour (int (int i=0;i<uiK;i++){pOutputArray[i]=pInputArray[i];}return true;}//partition partition function returns the index value of the quick row of the first element of array a index public static int partition(int[] a,int start,int end){int privot=a[start];int i=start;int j = end; while (i <j) {while (i <j && privot <= a [j]) {j -;} swap (a, i, j); while (i <j && privot> = a [i]) {i ++;} swap (a, i, j);} return i;} public static void swap (int [] a, int i, int j) {int t = a [i]; a [i] = a [j]; a [j] = t;}}} 2. Nombres avec plus de la moitié des événements du tableau
Il y a un nombre dans le tableau qui apparaît plus de la moitié de la longueur du tableau. Veuillez trouver ce numéro. Par exemple, 1, 2, 3, 2, 2, 5, 4, 2, le numéro 2 apparaît 5 fois dans le tableau, dépassant la moitié de la longueur du tableau, sortie 2
Inspiré par le tri rapide, en tri rapide, sélectionnez maintenant un numéro dans le tableau, puis ajustez l'ordre des nombres dans le tableau afin que les nombres plus petits que le nombre sélectionné soient classés sur sa gauche et les nombres plus grands que le nombre sélectionné sont classés à droite.
Si l'indice du numéro sélectionné se trouve être n / 2, alors ce numéro est le numéro médian dans le tableau
Importer java.util.scanner; public class Main {public static void main (string [] args) {scanner in = new scanner (system.in); int n = in.nextint (); int [] num = new int [n]; for (int i = 0; i <n; i ++) {num [i] = in.nextint ();} int b = gethalfnum (n, num); if (b! = - 1) {System.out.println (b);}} public static int gethalfnum (int uiInputNum, int [] pinputArray) {if (pinputArray == null || uiInputNum <= 0) {return -1;} int middle = uiinput start = 0; int end = uiInputNum-1; int index = partition (pinputArray, start, end); tandis que (index! = Middle) {// Si elle n'est pas égale à la moitié de la longueur, cela signifie que la médiane n'est pas trouvée si (index> middle) {end = index-1; index = partition (pignputArray, start, end);} else {start = index + 1; index = partition (pinputArray, start, end);}} return pinputarray [index]; // index = index = middle} public static int [] in, index]; // index). start, int end) {int privot = a [start]; int i = start; int j = end; while (i <j) {while (i <j && privot <= a [j]) {j -;} swap (a, i, j); while (i <j & privot> = a [i]) {i ++;} swap (a, i, j);} return i;} public static void swap (int [] a, int i, int j) {int t = a [i]; a [i] = a [j]; a [j] = t;}}} 3. Trouvez le Kth le plus petit nombre dans le tableau
Par exemple, étant donné le tableau 1, 5, 2, 6, 8, 0, 6, le 4ème plus petit nombre est 5
import java.util.scanner; public class main {public static void main (String [] args) {scanner in = new scanner (system.in); int n = in.nextint (); int k = in.nextint (); int [] num = new int [n]; // int [] out = new int [k]; for (int i = 0; i <n; i ++) {num [i] = in.nextint ();} int b = getMink (n, num, k); if (b! = - 1) {System.out.println (b);}} public static int GetMink (int uiInputNum, int [] pinputray, int stati uik) {if (pinputArray == null || uik> uiInputNum || uiInputNum <= 0 || uik <= 0) {return -1;} int start = 0; int end = uiInputNum-1; int index = partition (pinputArray, start, end); tandis que (index! = uik-1) {// si l'index n'est pas la position de K-1 if (index> uik-1) {end = index-1; index = partition (pignputArray, start, end);} else {start = index + 1; index = partition (pignputArray, start, end);}} return pinputArray [index]; // la valeur de cette position retournée} public static intra-partition (index]; end) {int privot = a [start]; int i = start; int j = end; while (i <j) {while (i <j && privot <= a [j]) {j -;} swap (a, i, j); while (i <j & privot> = a [i]) {i ++;} swap (a, i, j);} return i;} public static void swap (int [] a, int i, int j) {int t = a [i]; a [i] = a [j]; a [j] = t;}}}Résumer
Ce qui précède est l'intégralité du contenu de cet article sur l'exemple de code de trois questions d'algorithme basées sur le tri rapide de la programmation Java. J'espère que ce sera utile à tout le monde. Les amis intéressés peuvent continuer à se référer à d'autres sujets connexes sur ce site. S'il y a des lacunes, veuillez laisser un message pour le signaler. Merci vos amis pour votre soutien pour ce site!