用java写一个堆排序的函数,传入参数有int[],输出为void
时间: 2024-04-12 11:27:46 浏览: 41
好的,下面是一个用Java编写的堆排序函数:
```java
public static void heapSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
// 构建最大堆
buildMaxHeap(arr);
// 对堆进行排序
for (int i = arr.length - 1; i > 0; i--) {
// 将堆顶元素(最大值)与当前未排序部分的最后一个元素交换位置
swap(arr, 0, i);
// 调整堆,使其满足最大堆的性质
heapify(arr, 0, i);
}
}
// 构建最大堆
private static void buildMaxHeap(int[] arr) {
int len = arr.length;
// 从最后一个非叶子节点开始,依次进行堆化操作
for (int i = len / 2 - 1; i >= 0; i--) {
heapify(arr, i, len);
}
}
// 堆化操作,使以root为根节点的子树满足最大堆的性质
private static void heapify(int[] arr, int root, int heapSize) {
int largest = root; // 假设根节点最大
int left = 2 * root + 1; // 左子节点索引
int right = 2 * root + 2; // 右子节点索引
// 找出根节点、左子节点和右子节点中的最大值
if (left < heapSize && arr[left] > arr[largest]) {
largest = left;
}
if (right < heapSize && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大值不是根节点,则交换根节点和最大值
if (largest != root) {
swap(arr, root, largest);
// 递归调整交换后的子树
heapify(arr, largest, heapSize);
}
}
// 交换数组中两个元素的位置
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
```
这个函数使用堆排序算法对传入的整数数组进行排序,其中`arr`是待排序的数组。函数会直接修改原始数组,排序结果将保存在原数组中。请确保传入的参数合法有效。