Cet article décrit la méthode de mise en œuvre du tri de parité du tri d'échange Java. Partagez-le pour votre référence. Les détails sont les suivants:
Le tri de parité, le tri de transposition de parité, ou tri de brique, est un algorithme de tri relativement simple qui a été initialement inventé pour l'informatique parallèle avec des interconnexions locales. Il s'agit d'un type comparatif similaire aux caractéristiques du tri des bulles.
Dans cet algorithme, en comparant les paires numériques de position adjacentes (Odd-Even) dans le tableau, si la paire Odd-Even est dans le mauvais ordre (le premier est supérieur au second), puis échange. Répétez l'étape suivante, mais pour toutes les paires numériques de position (égal). Continuez comme ça alternativement.
Tri des tableaux de processeurs
Dans le tri parallèle de l'informatique, chaque processeur traite une valeur qui lui correspond et n'a que des interconnexions locales avec les voisins gauche et droit. Tous les processeurs peuvent comparer et échanger des opérations avec des voisins en même temps, alternativement dans un ordre étrange, même en même temps. L'algorithme a été initialement publié par Habermann en 1972 et a démontré son efficacité dans le traitement parallèle.
L'algorithme peut être étendu efficacement aux cas où chaque processeur a plusieurs valeurs. Dans l'algorithme de partitionnement de fusion de parité Baudetstevenson, chaque processeur trie les sous-réseaux qu'il possède à chaque étape, puis effectue une partition ou une transposition de fusion fusionnant avec les voisins.
Parité de Batcher et même tri
Le tri de parité de Batcher est un algorithme de tri pertinent mais plus efficace qui utilise des opérations d'échange de comparaison et d'allumage parfaites.
L'approche de Batcher est très efficace sur les processeurs informatiques parallèles avec une interconnexion étendue.
Pire complexité de temps / thêta (n ^ 2)
Le graphique dynamique de parité est le suivant:
Implémentation du code:
package com.baobaotao.test; : pre "> </span> * @param array <span style =" white-space: pre "> </span> * / public static void batchersort (int [] array) {int longueur = array.length; booléen drapeau Traid; while (true) {flag = true; , i + 1); drapeau = false;}} pour (int i = 0; i <longueur-1; i + = 2) , i + 1); à échanger b * @param c le nombre à échanger c * / public statique void swap (int [] a, int b, int c) {int temp = 0; ]> a [c]) {temp = a [b]; a [b] = a [c]; printarr (int [] array) {for (int c: array) {System.out.print (c + "");} System.out.println (); [] Numéro = {11,95,45,15,78,84,51,24,12};Analyse de sortie:
11 45 15 95 51 78 12 84 2411 15 45 51 12 95 24 78 8411 15 12 45 24 51 78 95 8411 12 15 24 45 51 78 84 95
J'espère que cet article sera utile à la programmation Java de tous.