Java中堆排序的案例分析

這篇文章將為大家詳細講解有關Java中堆排序的案例分析，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

一、引言

優先隊列可以用于以O(NlogN)時間排序。

二、圖解堆排序（heapsort）

1. 算法思想：通過將數組元素進行buildHeap進行堆序化（構建大頂堆）；再對堆進行N-1次deleteMax操作。這里有個技巧，如果使用新的數組來存儲，需要O(N)的空間；但每次deleteMax會空出一個位置，并將尾端的節點進行下濾操作，那我們就可以將deleteMax的數據放到尾端。
2. 堆排序過程：

對二叉堆不了解的可以看看圖解優先隊列（堆）

三、java代碼實現及時間復雜度分析

我們從數組下標0開始，不像二叉堆從數組下標1開始。

• 代碼實現

• 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)。

關于Java中堆排序的案例分析就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。