21xrx.com
2025-03-22 06:40:05 Saturday
文章检索 我的文章 写文章
Java堆排序:实现原理与代码示例
2023-06-16 09:31:42 深夜i     11     0
堆排序 大根堆 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),是一种非常高效的排序算法,适用于大数据量排序。除此之外,堆排序还具有空间复杂度低,稳定性好等优点。如果您对堆排序感兴趣,可以进一步了解一下其它排序算法的原理和代码实现。

  
  

评论区

请求出错了