Java堆排序：实现原理与代码示例 |21xrx.com

Java堆排序：实现原理与代码示例

2023-06-16 09:31:42 深夜i -- --

堆排序大根堆 Java实现

堆排序是一种高效的排序算法，它基于二叉堆的数据结构实现。在堆排序中，首先需要构造一个大（小）根堆，然后把堆顶元素和堆底元素交换，再将除堆底元素以外的元素继续构造大（小）根堆，并重复进行交换操作，直到整个序列有序为止。下面我们来看看Java实现堆排序的代码示例：


public class HeapSort {
  public static void sort(int[] arr) {
    int len = arr.length;
    for (int i = len / 2 - 1; i >= 0; i--)
      heapify(arr, len, i);
    for (int i = len - 1; i >= 0; i--) {
      swap(arr, 0, i);
      heapify(arr, i, 0);
    }
  }
  private static void heapify(int[] arr, int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    if (l < n && arr[l] > arr[largest])
      largest = l;
    if (r < n && arr[r] > arr[largest])
      largest = r;
    if (largest != i) {
      swap(arr, i, largest);
      heapify(arr, n, largest);
    }
  }
  private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

在上述代码中，我们首先利用堆的特性构造一个大根堆（如果需要构造小根堆，则需要将大于号换成小于号），接着进行交换操作，再对剩下的元素继续构造大（小）根堆，直到整个序列有序为止。需要注意的是，对于一个大小为n的堆，其最后一个非叶子节点的下标为 n/2-1，故我们需要从下标为n/2-1的节点开始构造堆。

堆排序的时间复杂度为O(nlogn)，是一种非常高效的排序算法，适用于大数据量排序。除此之外，堆排序还具有空间复杂度低，稳定性好等优点。如果您对堆排序感兴趣，可以进一步了解一下其它排序算法的原理和代码实现。

上一篇: idea打包java可执行jar包

下一篇: 如何在C语言中输出函数表达式的值

评论区

()

相似文章