Java 堆排序
堆排序(Heap Sort)是一种基于堆数据结构的比较排序算法。堆是一种特殊的完全二叉树,分为最大堆和最小堆。在最大堆中,每个节点的值都大于或等于其子节点的值;在最小堆中,每个节点的值都小于或等于其子节点的值。堆排序通常使用最大堆来实现升序排序。
以下是堆排序的基本步骤:
- 构建最大堆:将数组重新组织成一个最大堆。
- 交换堆顶元素和末尾元素:将堆顶元素(最大值)与当前未排序部分的末尾元素交换,此时末尾元素即为当前最大值。
- 调整堆:将交换后的堆(不包括已排序的末尾元素)重新调整为最大堆。
- 重复步骤2和3:直到所有元素都排序完毕。
下面是Java实现堆排序的代码:
public class HeapSort {
// 主方法
public static void main(String[] args) {
int[] array = {12, 11, 13, 5, 6, 7};
int n = array.length;
System.out.println("未排序数组:");
printArray(array);
heapSort(array, n);
System.out.println("排序后数组:");
printArray(array);
}
// 堆排序方法
public static void heapSort(int[] array, int n) {
// 构建最大堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(array, n, i);
}
// 一个个从堆顶取出元素,并调整堆
for (int i = n - 1; i >= 0; i--) {
// 将当前堆顶(最大值)移到数组末尾
int temp = array[0];
array[0] = array[i];
array[i] = temp;
// 调整堆,排除已排序的元素
heapify(array, i, 0);
}
}
// 调整堆
public static void heapify(int[] array, int n, int i) {
int largest = i; // 初始化父节点为最大值
int left = 2 * i + 1; // 左子节点
int right = 2 * i + 2; // 右子节点
// 如果左子节点存在且大于父节点
if (left < n && array[left] > array[largest]) {
largest = left;
}
// 如果右子节点存在且大于目前最大值
if (right < n && array[right] > array[largest]) {
largest = right;
}
// 如果最大值不是父节点
if (largest != i) {
int swap = array[i];
array[i] = array[largest];
array[largest] = swap;
// 递归调整受影响的子树
heapify(array, n, largest);
}
}
// 打印数组
public static void printArray(int[] array) {
int n = array.length;
for (int i = 0; i < n; ++i) {
System.out.print(array[i] + " ");
}
System.out.println();
}
}
代码解释:
- heapSort方法:
- 首先通过
for
循环构建最大堆,从最后一个非叶子节点开始调整堆。 - 然后通过另一个
for
循环,将堆顶元素(最大值)与当前未排序部分的末尾元素交换,并调整剩余部分的堆。
- 首先通过
- heapify方法:
- 用于调整堆,确保父节点大于其子节点。
- 找到左子节点和右子节点中较大的一个,并与父节点比较。
- 如果父节点不是最大的,则进行交换,并递归调整受影响的子树。
- printArray方法:
- 用于打印数组。
这样,通过堆排序算法,你可以有效地对数组进行排序。堆排序的时间复杂度为O(n log n),适合处理大数据集。
原文地址:https://blog.csdn.net/FlyingJiang/article/details/142831266
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!