Diagramme du processus de tri des tas d'apprentissage Java et explication du code

Cet article explique principalement le processus de tri des tas sous forme d'images, puis utilise du code Java pour implémenter le tri des tas et analyser la complexité temporelle. Il a une certaine valeur de référence et les amis intéressés peuvent en apprendre davantage.

1. Introduction2. Tri par tas graphique 3. Java implémentation du code et analyse de la complexité temporelle 4. Résumé

1. Introduction

La file d'attente prioritaire peut être utilisée pour trier en un temps O(NlogN), tout comme l'idée utilisée pour résoudre le problème topK dans l'article précédent, cette idée est un tri par tas.

2. Tri par tas graphique (heapsort)

1. Idée d'algorithme : Tri par tas en construisantHeap les éléments du tableau (build un grand tas supérieur), puis effectuez N-1 opérations deleteMax sur le tas. Voici une astuce. Si vous utilisez un nouveau tableau pour stocker, cela nécessitera un espace O(N) ; mais à chaque fois, deleteMax quittera une position et filtrera les nœuds de queue vers le bas, alors nous pourrons deleteMax. Les données sont placées à la fin.
2. Processus de tri du tas :

Si vous ne connaissez pas le tas binaire, vous pouvez jeter un œil à la file d'attente prioritaire illustrée (tas)

3. Implémentation du code Java et analyse de la complexité temporelle

Nous partons du tableau Il commence à l'index 0, contrairement au tas binaire qui commence à l'index 1 du tableau.

• Implémentation du code

• public class Heapsort {
      public static void main(String[] args) {
          Integer[] integers = {7, 1, 13, 9, 11, 5, 8};
          System.out.println("原序列：" + Arrays.toString(integers));
          heapsort(integers);
          System.out.println("排序后：" + Arrays.toString(integers));
      }
  
      public static <T extends Comparable<? super T>> void heapsort(T[] a) {
          if (null == a || a.length == 0) {
              throw new RuntimeException("数组为null或长度为0");
          }
          //构建堆
          for (int i = a.length / 2 - 1; i >= 0; i--) {
              percDown(a, i, a.length);
          }
          //deleteMax
          for (int i = a.length - 1; i > 0; i--) {
              swapReferences(a, 0, i);
              percDown(a, 0, i);
          }
      }
  
      /**
       * 下滤的方法
       *
       * @param a：待排序数组
       * @param i：从哪个索引开始下滤
       * @param n           ：二叉堆的逻辑大小
       * @param <T>
       */
      private static <T extends Comparable<? super T>> void percDown(T[] a, int i, int n) {
          int child;
          T tmp;
          for (tmp = a[i]; leftChild(i) < n; i = child) {
              child = leftChild(i);
              if (child != n - 1 && a[child].compareTo(a[child + 1]) < 0) {
                  child++;
              }
              if (tmp.compareTo(a[child]) < 0) {
                  a[i] = a[child];
              } else {
                  break;
              }
          }
          a[i] = tmp;
      }
  
      private static int leftChild(int i) {
          return 2 * i + 1;
      }
  
      /**
       * 交换数组中两个位置的元素
       *
       * @param a：目标数组
       * @param index1 ：第一个元素下标
       * @param index2 ：第二个元素下标
       * @param <T>
       */
      private static <T> void swapReferences(T[] a, int index1, int index2) {
          T tmp = a[index1];
          a[index1] = a[index2];
          a[index2] = tmp;
      }
  }
  //输出结果
  //原序列：[7, 1, 13, 9, 11, 5, 8]
  //排序后：[1, 5, 7, 8, 9, 11, 13]

• Complexité temporelle : buildHeap Utilisation O(N) temps, le filtrage des éléments nécessite O(logN) et le filtrage N-1 fois est requis, donc un total de O(N+(N-1)logN) = O(NlogN) est requis. Comme le montre le processus, quel que soit le meilleur ou le pire moment, la complexité du tri des tas est stable à O(NlogN).

• Complexité spatiale : Utilisant son propre stockage, il est sans aucun doute O(1).

4. Résumé

Cet article explique clairement le processus de tri des tas en dessinant une image Tas le tri est d'abord trié par tas, puis trié par deleteMax. Sa complexité spatiale est O(1) et sa complexité temporelle est stable à O(NlogN).

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!