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

Java堆排序实现：代码示例

2023-06-15 18:01:31 深夜i -- --

Java堆排序数组堆类

堆排序是常见的排序算法之一，它是一种选择排序，利用堆这种数据结构来实现。在本文中，我们将介绍Java中堆排序的实现方法，并提供代码示例进行讲解。

堆排序的基本思想是将待排序的序列构建成一个堆，然后依次选择最大元素放到堆的末尾，再将剩余的元素继续构建成堆，以此类推，直到所有元素都有序排列。在Java中，我们可以使用数组来实现堆排序。

我们定义一个堆类Heap，并在堆类中实现构建堆的方法buildHeap()和堆排序的方法heapSort()。代码如下：


class Heap {
  
  private int[] arr;
  private int len;
  
  public Heap(int[] arr)
    this.arr = arr;
    this.len = arr.length;
  
  
  // 构建堆
  public void buildHeap() {
    for (int i = len / 2 - 1; i >= 0; i--) {
      heapify(i);
    }
  }
  
  // 堆排序
  public void heapSort() {
    for (int i = len - 1; i >= 0; i--) {
      swap(0, i);
      len--;
      heapify(0);
    }
  }
  
  // 堆调整
  private void heapify(int i) {
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int largest = i;
    if (left < len && arr[left] > arr[largest])
      largest = left;
    
    if (right < len && arr[right] > arr[largest])
      largest = right;
    
    if (largest != i) {
      swap(i, largest);
      heapify(largest);
    }
  }
  
  // 数组元素交换
  private void swap(int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
  
  // 输出数组
  public void printArray() {
    for (int i : arr) {
      System.out.print(i + " ");
    }
    System.out.println();
  }
}
public class Main {
  
  public static void main(String[] args) {
    int[] arr = 8;
    Heap heap = new Heap(arr);
    heap.buildHeap();
    heap.heapSort();
    heap.printArray();
  }
}

在上面的代码中，我们首先定义了一个堆类Heap，该类包含了待排序的数组arr和数组长度len。接着我们实现了构建堆的方法buildHeap()和堆排序的方法heapSort()。在堆调整方法heapify()中，我们采用了递归的方式来实现堆的调整。最后，在主函数中创建了一个Heap对象，并调用它的构建堆方法、堆排序方法和输出数组方法。

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

下一篇: Java登陆界面代码及实现

评论区

()

相似文章