Diagramm des Java-Lern-Heap-Sortierprozesses und Code-Erklärung

Dieser Artikel erläutert hauptsächlich den Heap-Sortierungsprozess in Form von Bildern und verwendet dann Java-Code, um die Heap-Sortierung zu implementieren und die zeitliche Komplexität zu analysieren. Er hat einen bestimmten Referenzwert und interessierte Freunde können mehr darüber erfahren.

1. Einführung2. Grafische Heap-Sortierung 3. Java Code-Implementierung und Zeitkomplexitätsanalyse 4. Zusammenfassung

1. Einführung

Prioritätswarteschlange kann zum Sortieren in O(NlogN)-Zeit verwendet werden, genau wie die Idee, die bei der Lösung des topK-Problems im vorherigen Artikel verwendet wurde, diese Idee ist die Heap-Sortierung.

2. Grafische Heap-Sortierung (Heapsort)

1. Algorithmusidee: Heap-Sortierung durch BuildingHeapen Sie die Array-Elemente (Build einen großen oberen Heap); führen Sie dann N-1 deleteMax-Operationen auf dem Heap aus. Hier ist ein Trick. Wenn Sie ein neues Array zum Speichern verwenden, benötigt es O(N)-Speicherplatz, aber jedes Mal, wenn deleteMax eine Position freigibt und die Endknoten nach unten filtert, können wir deleteMax platzieren das Ende.
2. Heap-Sortierprozess:

Wenn Sie nichts über den binären Heap wissen, können Sie sich die abgebildete Prioritätswarteschlange (Heap) ansehen

3. Java-Code-Implementierung und Zeitkomplexitätsanalyse

Wir beginnen mit dem Array Es beginnt bei Index 0, im Gegensatz zu einem binären Heap, der bei Array-Index 1 beginnt.

• Code-Implementierung

• 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]

• Zeitkomplexität: buildHeap Using O(N) Zeit, das Herunterfiltern von Elementen erfordert O(logN) und das Herunterfiltern von N-1 Malen ist erforderlich, sodass insgesamt O(N+(N-1)logN) = O(NlogN) erforderlich ist. Wie aus dem Prozess ersichtlich ist, ist die Komplexität der Heap-Sortierung unabhängig von der besten oder schlechtesten Zeit stabil bei O(NlogN).

• Raumkomplexität: Unter Verwendung seines eigenen Speichers ist es zweifellos O(1).

4. Zusammenfassung

Dieser Artikel erklärt den Prozess der Heap-Sortierung anschaulich durch Zeichnen eines Bildes Heap sort ist zuerst Heap-sortiert und dann nach deleteMax sortiert. Seine räumliche Komplexität beträgt O(1) und seine Zeitkomplexität ist stabil bei O(NlogN).

Das obige ist der detaillierte Inhalt vonDiagramm des Java-Lern-Heap-Sortierprozesses und Code-Erklärung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!