algorithme de tri de structure de données Java (1) tri par sélection d'arbre

Cet article présente principalement l'arbre d'algorithme de tri de structure de données Java tri par sélection . Il analyse les principes, les techniques de mise en œuvre et les précautions associées au tri par sélection d'arbre Java sur la base d'exemples spécifiques auxquels vous pouvez vous référer. ce qui suit

Cet article décrit le tri par sélection d'arborescence de l'algorithme de tri de structure de données Java à titre d'exemple. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

Ici, nous parlerons du tri de l'un des types de sélection : tri par sélection d'arbre

Dans le tri par sélection simple, chaque comparaison Les résultats de la dernière comparaison ne sont pas utilisés, donc la complexité temporelle de l'opération de comparaison est O(N^2) Si vous souhaitez réduire le nombre de comparaisons, vous devez enregistrer la relation de taille pendant. le processus de comparaison. Le tri par sélection arborescente est une amélioration par rapport au tri par sélection simple.

Tri par sélection d'arbre : , également connu sous le nom de Tournoi Tri) , est un tri basé sur le championnat Pensez de façons d'effectuer un tri de sélection. Effectuez d'abord une comparaison par paire des mots-clés de n enregistrements, puis effectuez une comparaison par paire entre les n/2 plus petits, et répétez cette opération jusqu'à ce que le plus petit enregistrement soit sélectionné.

Le code d'implémentation de l'algorithme est le suivant :

package exp_sort;
public class TreeSelectSort {
 public static int[] TreeSelectionSort(int[] mData) {
  int TreeLong = mData.length * 4;
  int MinValue = -10000;
  int[] tree = new int[TreeLong]; // 树的大小
  int baseSize;
  int i;
  int n = mData.length;
  int max;
  int maxIndex;
  int treeSize;
  baseSize = 1;
  while (baseSize < n) {
   baseSize *= 2;
  }
  treeSize = baseSize * 2 - 1;
  for (i = 0; i < n; i++) {
   tree[treeSize - i] = mData[i];
  }
  for (; i < baseSize; i++) {
   tree[treeSize - i] = MinValue;
  }
  // 构造一棵树
  for (i = treeSize; i > 1; i -= 2) {
   tree[i / 2] = (tree[i] > tree[i - 1] ? tree[i] : tree[i - 1]);
  }
  n -= 1;
  while (n != -1) {
   max = tree[1];
   mData[n--] = max;
   maxIndex = treeSize;
   while (tree[maxIndex] != max) {
    maxIndex--;
   }
   tree[maxIndex] = MinValue;
   while (maxIndex > 1) {
    if (maxIndex % 2 == 0) {
     tree[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex + 1] ? tree[maxIndex]
       : tree[maxIndex + 1]);
    } else {
     tree[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex - 1] ? tree[maxIndex]
       : tree[maxIndex - 1]);
    }
    maxIndex /= 2;
   }
  }
  return mData;
 }
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
  TreeSelectionSort(array);
  for (int i = 0; i < array.length; i++) {
   System.out.print(array[i] + " ");
  }
  System.out.println("\n");
 }
}

Analyse de l'algorithme :

Dans le tri par sélection d'arbre, à l'exception du plus petit mot-clé, le plus petit mot-clé sélectionné passe tous par un processus de comparaison des nœuds feuilles aux nœuds suivants puisqu'un arbre binaire complet contenant n nœuds feuilles a La profondeur est log2n+1. .Par conséquent, dans le tri par sélection arborescente, chaque fois qu'un mot-clé plus petit est sélectionné, des comparaisons log2n sont nécessaires, donc la complexité temporelle est de O(nlog2n). Le nombre d'enregistrements déplacés ne dépasse pas le nombre de comparaisons, donc l'algorithme total Le temps. la complexité est O(nlog2n). Par rapport à l'algorithme de tri par sélection simple, le nombre de comparaisons est réduit d'un ordre de grandeur et n-1 espace de stockage supplémentaire est ajouté pour stocker les résultats de comparaison intermédiaire.

Supplément :

Nous introduisons ici un algorithme amélioré pour le tri par sélection d'arbres, à savoir l'algorithme de tri par tas.

Le tri par tas compense le défaut de l'algorithme de tri par sélection arborescente qui prend beaucoup de place. Lors de l'utilisation du tri par tas, un seul espace auxiliaire de la taille d'un enregistrement est requis.

L'idée de l'algorithme est :

Stocker les mots-clés des enregistrements à trier dans le tableaur[1.. .n], et set r Il est considéré comme une représentation séquentielle d'un arbre binaire complet. Chaque nœud représente un enregistrement. Le premier enregistrement r[1] est utilisé comme racine de l'arbre binaire suivant. 2...n] est superposé de gauche à droite. Disposé dans l'ordre de droite, l'enfant gauche de tout nœud r[i] est r[2*i], l'enfant droit est r[2*i+1] ; le parent est r[[i/2]].

Définition du tas : La valeur clé de chaque nœud satisfait aux conditions suivantes :

r[i].key >= r[2i].key et r[ i].key >= r[2i+1].key (i=1,2,...[i/2])

Un arbre binaire complet qui remplit les conditions ci-dessus est appelé un grand tas racine; au contraire, si La clé de n'importe quel nœud dans cet arbre binaire complet est inférieure ou égale à la clé de son enfant gauche et de son enfant droit, et le tas correspondant est appelé un petit tas racine.

Le processus de tri des tas doit principalement résoudre deux problèmes : le premier consiste à construire un tas initial selon la définition du tas ; le second consiste à reconstruire le tas après avoir supprimé le plus grand élément pour obtenir le sous-plus grand. élément.

Le tri par tas consiste à utiliser les caractéristiques du tas pour trier la séquence d'enregistrements. Le processus est le suivant :

1 Construisez un tas pour la séquence donnée
2. le haut du tas ; (premier élément Échange avec l'élément de queue)
3. Reconstruisez le tas avec les éléments restants ; (filtrez le premier élément)
4. Répétez les étapes 2 et 3 jusqu'à ce que tous les éléments soient affichés.

Remarque : Le "Filtrage" doit commencer à partir du [n/2]ème nœud et remonter couche par couche jusqu'au nœud racine.

Analyse d'algorithme :

1 Pour un tas d'une profondeur de k, le nombre de comparaisons de mots clés requis pour le « filtrage » est d'au plus 2(k-1. ) ;
2. La profondeur du tas de n mots-clés est [log2n]+1, et le nombre de comparaisons de mots-clés requis pour construire initialement le tas est au maximum : n* [log2n];
3. n- 1 fois, le nombre de comparaisons de mots clés requises ne dépasse pas : (n-1)*2 [log2n]

Par conséquent, dans le pire des cas, la complexité temporelle du tri par tas est O(nlog2n ) , c'est le plus grand avantage du tri par tas.

[Recommandations associées]

1. Tutoriel détaillé sur le tri par sélection (Selection Sort_java) en Java

2 Tri de la structure des données Java. algorithme (2) Tri par fusion

3. Algorithme de tri de structure de données Java (3) Tri par sélection simple

4. (4) Tri de sélection

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!