Exemple d'analyse de l'algorithme de tri par tas en Java

Cet article présente principalement en détail le code pertinent de l'algorithme de tri du tas Java. Il a une certaine valeur de référence. Les amis intéressés peuvent s'y référer

Le tas est un type important de structure de données, comprenant le concept. et le fonctionnement du « tas » peut nous aider à maîtriser rapidement le tri des tas.

Le concept de tas

Un tas est un arbre binaire complet spécial. Si la valeur de tous les nœuds d'un arbre binaire complet n'est pas inférieure à celle de ses nœuds enfants, on l'appelle un grand tas racine (ou grand tas supérieur) ; un petit tas de racine (ou petit tas supérieur).

Dans le tableau (le nœud racine est stocké à l'indice 0), il est facile d'obtenir la formule suivante (ces deux formules sont très importantes) :

1 Le nœud avec l'indice i. , les coordonnées du nœud parent sont (i-1)/2 ;

2. Pour le nœud dont l'indice est i, les coordonnées du nœud enfant gauche sont 2*i+1 et le nœud enfant droit. est 2*i+2.

Création et maintenance du tas

Le tas peut prendre en charge diverses opérations, mais nous ne nous préoccupons désormais que de deux problèmes :

1 .Étant donné un tableau non ordonné, comment le construire sous forme de tas ?

2. Après avoir supprimé l'élément supérieur du tas, comment ajuster le tableau dans un nouveau tas ?

Regardons d’abord la deuxième question. Supposons que nous ayons déjà un gros tas de racines prêt à fonctionner. Nous avons maintenant supprimé l'élément racine, mais n'avons déplacé aucun autre élément. Pensez à ce qui se passe : l'élément racine est vide, mais les autres éléments conservent la nature du tas. Nous pouvons déplacer le dernier élément (nom de code A) vers la position de l'élément racine. Si ce n’est pas un cas particulier, la nature du tas est détruite. Mais c’est uniquement parce que A est plus petit qu’un de ses enfants. Par conséquent, nous pouvons échanger les positions de A et de ce sous-élément. Si A est plus grand que tous ses sous-éléments, le tas est ajusté ; sinon, le processus ci-dessus est répété et l'élément A continue de "s'enfoncer" dans la structure arborescente jusqu'à ce que la position appropriée soit atteinte, et le tableau retrouve son tas. propriétés. Le processus ci-dessus est généralement appelé « sélection » et la direction est évidemment descendante.

Il en va de même pour la suppression d'un élément, et il en va de même pour l'insertion d'un nouvel élément. La différence est que nous plaçons le nouvel élément à la fin, puis le comparons avec son nœud parent, c'est-à-dire un filtrage ascendant.

Alors, comment résoudre le premier problème ?

La plupart des livres sur la structure des données que j'ai lus filtrent à partir du premier nœud non-feuille jusqu'à ce que l'élément racine soit filtré. Cette méthode est appelée « méthode de filtrage » et nécessite un bouclage pour filtrer n/2 éléments.

Mais on peut aussi s'inspirer de l'idée de "faire quelque chose à partir de rien". Nous pouvons traiter le premier élément comme un tas et continuer à y ajouter de nouveaux éléments. Cette méthode est appelée « méthode d'insertion » et nécessite l'insertion de (n-1) éléments dans une boucle.

Étant donné que la méthode de filtrage et la méthode d'insertion sont différentes, les tas qu'elles créent pour les mêmes données sont généralement différents.

Après avoir une compréhension générale des tas, le tri des tas est une évidence.

Aperçu/idées de l'algorithme

Nous avons besoin d'une séquence ascendante, que devons-nous faire ? Nous pouvons créer un min-heap, puis afficher l'élément racine à chaque fois. Cependant, cette méthode nécessite de l'espace supplémentaire (sinon elle entraînera le déplacement d'un grand nombre d'éléments et sa complexité montera jusqu'à O(n^2)). Que se passe-t-il si nous devons trier sur place (c'est-à-dire que la complexité de l'espace O(n) n'est pas autorisée) ?
Il existe un moyen. Nous pouvons construire un tas maximum, puis nous le produisons à l'envers, en produisant la valeur maximale à la dernière position et en produisant la deuxième plus grande valeur à la dernière position... Puisque la sortie du plus grand élément à chaque fois libérera le premier espace. , nous pouvons simplement placer de tels éléments sans espace supplémentaire. Jolie idée, n'est-ce pas ?

public class HeapSort 
{
  public static void main(String[] args) 
  {
    int[] arr = { 50, 10, 90, 30, 70, 40, 80, 60, 20 };
    System.out.println("排序之前："); 
    for (int i = 0; i < arr.length; i++) 
      System.out.print(arr[i] + " "); 
    
    // 堆排序
    heapSort(arr); 
    System.out.println(); 
    System.out.println("排序之后："); 
    for (int i = 0; i < arr.length; i++) 
      System.out.print(arr[i] + " ");
  }
  
  /** 
  * 堆排序 
  */
  private static void heapSort(int[] arr) 
  {
    // 将待排序的序列构建成一个大顶堆 
    for (int i = arr.length / 2; i >= 0; i--)
      heapAdjust(arr, i, arr.length);
    
    // 逐步将每个最大值的根节点与末尾元素交换，并且再调整二叉树，使其成为大顶堆 
    for (int i = arr.length - 1; i > 0; i--)
    {
      swap(arr, 0, i); // 将堆顶记录和当前未经排序子序列的最后一个记录交换 
      heapAdjust(arr, 0, i); // 交换之后，需要重新检查堆是否符合大顶堆，不符合则要调整
    }
  }
  /** 
  * 构建堆的过程 
  * @param arr 需要排序的数组 
  * @param i 需要构建堆的根节点的序号 
  * @param n 数组的长度 
  */
  private static void heapAdjust(int[] arr, int i, int n) 
  {
    int child;
    int father;
    for (father = arr[i]; leftChild(i) < n; i = child)
    {
      child = leftChild(i);
      // 如果左子树小于右子树，则需要比较右子树和父节点 
      if (child != n - 1 && arr[child] < arr[child + 1])
        child++; // 序号增1，指向右子树
      // 如果父节点小于孩子结点，则需要交换 
      if (father < arr[child]) 
        arr[i] = arr[child];
      else
        break; // 大顶堆结构未被破坏，不需要调整
    }
    arr[i] = father;
  }
  
  // 获取到左孩子结点 
  private static int leftChild(int i) 
  {
    return 2 * i + 1;
  }
  
  // 交换元素位置 
  private static void swap(int[] arr, int index1, int index2) 
  {
    int tmp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = tmp;
  }
}

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!