Java学習ヒープのソート処理図とコードの説明

この記事では、主にヒープ ソートのプロセスを図で説明し、Java コードを使用してヒープ ソートを実装し、時間計算量を分析します。一定の参考価値があり、興味のある友人はさらに学ぶことができます。

1. はじめに2. 図解ヒープソート 3. Java コード実装と時間計算量の分析 4. まとめ

## 1. はじめに

Priority キューを使用すると、O(NlogN) 時間でソートできます。前の記事で topK 問題を解決するときに使用したアイデアと同じように、このアイデアはヒープ ソート (ヒープソート) です。

2. グラフィカル ヒープ ソート (heapsort)

1. アルゴリズムのアイデア: build によるヒープ ソートHeap 配列要素 (build)大きな上部ヒープ)、その後、ヒープに対して N-1 個の deleteMax 操作を実行します。 ここにトリックがあります。新しい配列を使用して保存する場合、O(N) スペースが必要になります。しかし、deleteMax が位置を空けて末尾ノードをフィルタリングするたびに、deleteMax データは次の場所に配置されます。終わり。
2. ヒープの並べ替えプロセス:

バイナリ ヒープについてわからない場合は、グラフィック優先キュー (ヒープ) を見てください。 ##

3. Java コードの実装と時間計算量の分析

配列から始めます配列インデックス 1 から始まるバイナリ ヒープとは異なり、インデックス 0 から始まります。

• コードの実装

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

• 時間計算量: buildHeap の使用O(N) 回、要素のフィルタリングには O(logN) が必要で、N-1 回のフィルタリングが必要なので、合計 O(N (N-1)logN) = O(NlogN) が必要です。 このプロセスから、ヒープのソートは、時間計算量が最高か最低かに関わらず、 O(NlogN) で安定していることがわかります。

• スペースの複雑さ: 独自のストレージを使用することは間違いなく O(1) です。

##4. 概要

この記事では、描画によるヒープのソートのプロセスをわかりやすく説明します

ヒープソートは、まずヒープソートされ、次に deleteMax によってソートされます。その空間計算量は O(1) で、時間計算量は O(NlogN) で安定しています。

以上がJava学習ヒープのソート処理図とコードの説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。