Cet article décrit l'opération de sélection de temps linéaire implémentée par Java en fonction de l'algorithme de partitionnement et de conquête. Partagez-le pour votre référence, comme suit:
Problème de sélection du temps linéaire: Compte tenu des éléments n et un entier k, 1≤k≤n, il est nécessaire de découvrir le plus petit élément de ces n éléments (l'ensemble linéaire donné ici est désordonné).
Sélection linéaire divisée au hasard
La méthode de division aléatoire de sélection de temps linéaire peut imiter la conception de l'algorithme de tri rapide randomisé. L'idée de base est de diviser récursivement le tableau d'entrée. Contrairement au tri rapide, il ne traite que de manière récursive l'un des sous-réseaux divisés.
Explication du programme: Utilisez une fonction aléatoire pour générer une référence de division, divisez le tableau A [P: R] en deux sous-réseaux A [P: I] et A [i + 1: R], de sorte que chaque élément dans un [P: I] n'est pas plus grand que chaque élément dans un [i + 1: R]. Alors "j = i-p + 1" calcule le nombre d'éléments j dans un [p: i]. Si k <= j, alors le K-th le plus petit élément d'un [P: R] est dans le sous-tableau A [P: I], et si K> J, le plus petit élément est dans le sous-tableau A [i + 1: r]. Remarque: Puisqu'il est connu que les éléments du sous-tableau A [P: I] sont tous plus petits que le petit élément K -th à trouver, le petit élément K -th dans A [P: R] est le petit élément K -th dans un [i + 1: R].
Dans le pire des cas, par exemple: lorsque le plus petit élément est toujours trouvé, il est toujours divisé au plus grand élément, qui est la complexité temporelle de O (n ^ 2) . Cependant, la complexité du temps moyenne est linéairement liée à n, qui est O (n)
package math; import java.util.scanner; import java.util.random; public class randomselect {public static void swap (int x, int y) {int temp = x; x = y; y = temp; } public int random (int x, int y) {random random = new random (); int num = random.nextint (y)% (y - x + 1) + x; retour num; } public int partition (int [] list, int low, int high) {int tmp = list [low]; // Le premier du tableau est l'axe central tandis que (Low <High) {while (Low <high && list [high]> tmp) {high--; } list [low] = list [high]; // Les enregistrements plus petits que l'axe central sont déplacés vers l'extrémité bas tandis que (Low <High && list [Low] <TMP) {Low ++; } list [high] = list [Low]; // enregistre plus grand que l'axe central est déplacé vers la liste haut de gamme} [bas] = TMP; // enregistre plus grand que l'axe central est renvoyé bas; // Retour à la position de l'axe central} public int randomizedPartition (int [] Arrays, int Left, int droit) {int i = random (gauche, droite); swap (tableaux [i], tableaux [gauche]); Partition de retour (tableaux, gauche, droite); } public int randomizedSelect (int [] Arrays, int Left, int droite, int k) {if (Left == droite) {return Arrays [Left]; } int i = randomizedPartition (tableaux, gauche, droite); int j = i - gauche + 1; if (k <= j) {return randomizedSelect (tableaux, à gauche, i, k); } else {return randomizedSelect (tableaux, i + 1, à droite, kj); }} public static void main (String args []) {System.out.println ("Wulin.com Résultat du test:"); int [] a = {7,5,3,4,8,6,9,1,2}; pour (int i = 0; i <9; i ++) {System.out.print (a [i] + ""); } System.out.println (); RandomSelect r = new RandomSelect (); System.out.println ("Quel plus petit élément souhaitez-vous interroger dans le tableau?"); @SuppressWarnings ("Resource") Scanner SC = nouveau scanner (System.in); int m = sc.nextint (); int n = r.randomizedSelect (a, 0,8, m); System.out.println ("le" th "dans ce tableau" + m + "Le plus petit élément est:" + n); }}Résultats en cours:
Pour plus d'informations sur les algorithmes Java, les lecteurs qui sont intéressés par ce site peuvent afficher les sujets: "Structure de données Java et tutoriel d'algorithme", "Résumé des conseils de nœud de Dom Operation Java", "Résumé du fichier Java et des conseils d'opération de répertoire" et "Résumé des conseils d'opération Java Cache"
J'espère que cet article sera utile à la programmation Java de tous.