Java实现堆排序——将数据结构变得更好 |21xrx.com

Java实现堆排序——将数据结构变得更好

2023-06-15 00:43:24 深夜i -- --

Java 堆排序算法

堆排序是一种高效的排序算法，它可以将无序的数据序列排序，时间复杂度为O（nlogn）。在实际开发中，使用堆排序可以帮助我们处理大量的数据，提高程序的效率。

下面就给大家介绍一下，如何使用Java实现堆排序。

首先，我们需要先了解什么是堆。堆是一种完全二叉树，树中每个节点的值都不小于（或不大于）其左右孩子节点的值。

我们可以使用数组来模拟二叉树，根据父节点序号，求出其对应的左右孩子节点的序号。具体代码实现如下：


public static int leftChild(int i){
  return (i * 2) + 1;
}
public static int rightChild(int i){
  return (i * 2) + 2;
}

接下来，我们需要实现堆排序的主要算法。这里我们使用大顶堆来进行排序，即每个父节点都比其孩子节点的值大。

具体实现如下：


public static void heapSort(int[] arr){
  if(arr == null || arr.length < 2)
    return;
  
  //1.将原数组构造成大根堆
  int heapSize = arr.length;
  for(int i = 0; i < heapSize; i++){
    heapInsert(arr, i);
  }
  //2.将堆顶元素与数组末尾元素交换，维护大根堆
  while(heapSize > 0){
    swap(arr, 0, --heapSize);
    heapify(arr, 0, heapSize);
  }
}
/**
* 插入新元素到堆中，使其成为一棵大根堆
*/
public static void heapInsert(int[] arr, int i){
  while(arr[i] > arr[(i - 1) / 2]){
    swap(arr, i, (i - 1) / 2);
    i = (i - 1) / 2;
  }
}
/**
* 将堆顶元素换到正确的位置，以维护大根堆
*/
public static void heapify(int[] arr, int i, int heapSize){
  int left = leftChild(i);
  int right = rightChild(i);
  int largest = i;
  if(left < heapSize && arr[left] > arr[largest])
    largest = left;
  
  if(right < heapSize && arr[right] > arr[largest])
    largest = right;
  
  if(largest != i){
    swap(arr, i, largest);
    heapify(arr, largest, heapSize);
  }
}
/**
* 交换数组两个位置的值
*/
public static void swap(int[] arr, int i, int j){
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

通过上述代码实现，我们就可以使用Java实现堆排序了。

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

下一篇: Java文件后缀名是什么？- Java代码案例

评论区

()

相似文章