21xrx.com
2024-11-08 21:11:57 Friday
登录
文章检索 我的文章 写文章
实现Java堆排序的工具类
2023-06-12 01:38:46 深夜i     --     --
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堆排序工具类的实现代码和用法。希望能对大家有所帮助。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复