21xrx.com
2025-04-22 08:31:15 Tuesday
文章检索 我的文章 写文章
实现Java堆排序的工具类
2023-06-12 01:38:46 深夜i     19     0
Java 堆排序 工具类

Java提供了许多常用的排序算法，其中堆排序算法是非常高效的。本文将介绍如何实现一个Java堆排序的工具类，并提供相应的代码案例。

首先，我们需要定义一个工具类来实现堆排序。该类应包含一个静态方法sort，用于对传入的数组进行排序。以下是该类的代码实现：

public class HeapSort {
  public static void sort(int[] arr) {
    int n = arr.length;
    // Build heap (rearrange array)
    for (int i = n / 2 - 1; i >= 0; i--) {
      heapify(arr, n, i);
    }
    // One by one extract an element from heap
    for (int i = n - 1; i >= 0; i--) {
      // Move current root to end
      int temp = arr[0];
      arr[0] = arr[i];
      arr[i] = temp;
      // call max heapify on the reduced heap
      heapify(arr, i, 0);
    }
  }
  // To heapify a subtree rooted with node i which is an index in arr[].
  // n is size of heap
  static void heapify(int[] arr, int n, int i) {
    int largest = i; // Initialize largest as root
    int l = 2 * i + 1; // left = 2*i + 1
    int r = 2 * i + 2; // right = 2*i + 2
    // If left child is larger than root
    if (l < n && arr[l] > arr[largest])
      largest = l;
    // If right child is larger than largest so far
    if (r < n && arr[r] > arr[largest])
      largest = r;
    // If largest is not root
    if (largest != i) {
      int swap = arr[i];
      arr[i] = arr[largest];
      arr[largest] = swap;
      // Recursively heapify the affected sub-tree
      heapify(arr, n, largest);
    }
  }
}

使用该工具类进行排序的代码非常简单：

int[] arr = 7;
HeapSort.sort(arr);
//arr现在已经按照从小到大的顺序排好了序

以上就是Java堆排序工具类的实现代码和用法。希望能对大家有所帮助。

  
  

评论区