Java实现堆排序，演示高效的排序算法 |21xrx.com

Java实现堆排序，演示高效的排序算法

2023-06-17 15:28:07 深夜i -- --

Java 堆排序二叉堆

堆排序是一种高效的排序算法，采用二叉堆的数据结构实现，能够在最坏情况下保持 O(nlogn) 的时间复杂度。本文将演示如何在 Java 中实现堆排序，并提供代码案例和实验结果。

Java 实现堆排序的步骤如下：

1. 将待排序的数组构建成二叉堆。

2. 从最后一个非叶子节点开始进行堆调整。

3. 按照顺序将每颗子树调整为最大堆。

4. 将堆顶元素与最后一个元素互换，然后重新调整堆。

下面是 Java 实现堆排序的完整代码：


public class HeapSort {
  public 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);
    }
  }
  void heapify(int[] arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && arr[left] > arr[largest])
      largest = left;
    
    if (right < n && arr[right] > arr[largest])
      largest = right;
    
    if (largest != i) {
      swap(arr, i, largest);
      heapify(arr, n, largest);
    }
  }
  void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
  public static void main(String[] args) {
    int[] arr = 13;
    HeapSort heapSort = new HeapSort();
    heapSort.sort(arr);
    System.out.println(Arrays.toString(arr));
  }
}

运行结果如下：


[5, 6, 7, 11, 12, 13]

可以看出，堆排序能够非常高效地对数组进行排序。

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

下一篇: C语言实现数组倒序输出

评论区

()

相似文章