Tri par tas de tri JAVA

L'éditeur ci-dessous vous proposera un tri par tas de tri par comparaison à l'ancienne. L'éditeur le trouve plutôt bon, je vais donc le partager avec vous maintenant et le donner comme référence pour tout le monde. Suivons l'éditeur et jetons un coup d'œil

Le tri par tas impliquera une connaissance complète de l'arbre binaire. Pour que la séquence soit triée {10, 2, 11, 8, 7}, considérez-la comme un arbre binaire complet, comme le montre la figure ci-dessous.

Le tas est divisé en un grand tas racine et un petit tas racine : le grand tas racine signifie que chaque nœud racine est plus grand que ses nœuds enfants (L(i) >= L(2i) && L(i) >= L(2i + 1)), le petit tas racine signifie que chaque nœud racine est plus petit que son nœud enfant (L(i) <= L(2i) && L(i) <= L( 2i + 1)). (Dans un arbre binaire complet, le nœud enfant gauche du i-ème nœud est 2i, et son nœud octet droit est 2i + 1)

Cet article expliquera la construction d'un un grand tas de racines à titre d'exemple.

La première étape du tri des tas : la construction du tas initial. Comment construire le tas initial ? Par définition, le point clé réside dans chaque nœud racine. En observant l'arbre binaire complet de la séquence mentionnée ci-dessus à trier, il n'est pas difficile de constater que le nœud 2 et le nœud 10 ont des nœuds enfants, qui sont les nœuds qui nécessitent une attention particulière.

Comment localiser le nœud 2 ? On constate qu'il s'agit d'un nœud feuille, ou du nœud parent du dernier nœud. Selon les propriétés d'un arbre binaire complet, le numéro du nœud parent de tout nœud à l'exception du nœud racine est ⌊n / 2⌋. Sachant que n = 5, il est facile de savoir que le numéro du nœud 2 est ⌊5 / 2⌋ = ②. Comparez-le à la taille des nœuds enfants gauche et droit et ajustez.

Enfin, le nœud racine 10 est laissé. Le numéro du nœud 2 est connu comme étant ②, ② - 1 = ①, ce qui signifie que le numéro du nœud racine 10 est. obtenu. Comparez-le à la taille des nœuds enfants gauche et droit et ajustez.

Une fois l'ajustement terminé, on constate qu'un « gros tas de racines » s'est formé. La colonne à trier dans l'exemple est relativement simple, et un plus. une colonne complexe à trier est donnée pour observer son processus de construction d'un gros tas de racines. Pour que la séquence soit triée {53, 17, 78, 09, 45, 65, 87, 32}, traitez-la comme un arbre binaire complet.

De même, regardons les nœuds auxquels il doit prêter attention.

Selon le premier exemple, on peut facilement localiser le numéro du nœud 09 comme ⌊8 / 2⌋ = ④, et le numéro du nœud 78 comme ④ - 1 = ③… ..., et ainsi de suite, un certain modèle est trouvé, c'est-à-dire que la position du nœud qui doit être ajustée pour est de ⌊n/2⌋ Commencez à diminuer en séquence jusqu'à la fin du nœud racine ① (⌊n/2⌋~1). Commencez à vous ajuster maintenant.

Découvert après le quatrième ajustement effectué par Node 53 ne répond pas à la définition d'un grand tas racine et que son nœud enfant droit est plus grand que lui. À ce stade, un ajustement supplémentaire vers le bas est nécessaire.

Notez que des ajustements à la baisse doivent être effectués chaque fois qu'un ajustement à la hausse est effectué pour déterminer si un ajustement à la baisse est nécessaire, plutôt que de regarder en arrière une fois que tous les ajustements à la hausse sont terminés. Ajustez vers le bas. De cette façon, le grand tas racine est établi et la situation du tableau de colonnes à trier a changé : {87, 45, 78, 32, 17, 65, 53, 09}. Reste ensuite la question de savoir comment trier. Échangez le nœud racine du grand tas racine avec le dernier nœud et ajustez l'arbre binaire afin qu'il satisfasse toujours le grand tas racine.

Vous pouvez voir qu'après avoir appelé le nœud racine et le dernier nœud, la valeur maximale de la colonne à trier a été placée à la dernière position du tableau {..., 87}. le tri est terminé, mais ce premier tri par passes n'est pas encore terminé. À l'exception du nœud 87, les autres nœuds ne remplissent pas les conditions du grand tas racine, les nœuds restants doivent donc être ajustés à la grande racine. tas. Le processus de tri n'est plus donné. L'implémentation du code en Java et Python3 est la suivante.

Java

package com.algorithm.sort.heap;

import java.util.Arrays;

/**
 * 堆排序
 * Created by yulinfeng on 6/20/17.
 */
public class Heap {
  
  public static void main(String[] args) {
    int[] nums = {53, 17, 78, 09, 45, 65, 87, 32};
    nums = heapSort(nums);
    System.out.println(Arrays.toString(nums));
  }
  
  /**
   * 堆排序
   * @param nums 待排序数组序列
   * @return 排好序的数组序列
   */
  private static int[] heapSort(int[] nums) {
  
    for (int i = nums.length / 2 - 1; i >= 0; i--) {
      heapAdjust(nums, i, nums.length);
    }
    for (int i = nums.length - 1; i > 0; i--) {
      int temp = nums[i];
      nums[i] = nums[0];
      nums[0] = temp;
      heapAdjust(nums, 0, i);
    }
    return nums;
  }
  
  /**
   * 调整堆
   *
   * @param nums  待排序序列
   * @param parent   待调整根节点
   * @param length 数组序列长度
   */
  private static void heapAdjust(int[] nums, int parent, int length) {
    int temp = nums[parent];
    int childIndex = 2 * parent + 1;  //完全二叉树节点i从编号1开始的左子节点位置在2i，此处数组下标从0开始，即左子节点所在数组索引位置为：2i + 1
    while (childIndex < length) {
      if (childIndex + 1 < length && nums[childIndex] < nums[childIndex + 1]) {
        childIndex++;  //节点有右子节点，且右子节点大于左子节点，则选取右子节点
      }
      if (temp > nums[childIndex]) {
        break; //如果选中节点大于其子节点，直接返回
      }
      nums[parent] = nums[childIndex];
      parent = childIndex;
      childIndex = 2 * parent + 1;  //继续向下调整
    }
    nums[parent] = temp;
  }
}

Python3

#堆排序
def heap_sort(nums):

  for i in range(int(len(nums) / 2 - 1), -1, -1):
    heap_adjust(nums, i, len(nums))
  
  for i in range(len(nums) - 1, -1, -1):
    temp = nums[i]
    nums[i] = nums[0]
    nums[0] = temp
    heap_adjust(nums, 0, i)
  
  return nums

#调整堆
def heap_adjust(nums, parent, length):
  
  temp = nums[parent]
  childIndex = 2 * parent + 1
  while childIndex < length:
    if childIndex + 1 < length and nums[childIndex] < nums[childIndex + 1]:
      childIndex += 1
    if temp > nums[childIndex]:
      break
    nums[parent] = nums[childIndex]
    parent = childIndex
    childIndex = 2 * parent + 1
  
  nums[parent] = temp
    
nums = [53, 17, 78, 09, 45, 65, 87, 32]
nums = heap_sort(nums)
print(nums)

Le tri par comparaison des clichés et le tri par tas ci-dessus sont tout le contenu partagé par l'éditeur. J'espère qu'il pourra vous donner une référence et j'espère que vous soutiendrez Script Home.

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!