堆排序
堆排序(Heap Sort)是一种基于比较的排序算法,利用堆这种数据结构来进行排序。堆是一种完全二叉树,具有以下性质:对于每个节点,节点的值总是大于或等于(或小于或等于)其子节点的值。根据这个性质,堆可以分为最大堆和最小堆。
下面是一个使用Java实现的堆排序的示例代码:
public class HeapSort {
// 主方法
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
System.out.println("原始数组:");
printArray(arr);
heapSort(arr);
System.out.println("排序后的数组:");
printArray(arr);
}
// 堆排序方法
public static void heapSort(int[] arr) {
int n = arr.length;
// 构建最大堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 一个个提取元素
for (int i = n - 1; i > 0; i--) {
// 将当前根节点(最大值)与最后一个节点交换
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 调整堆
heapify(arr, i, 0);
}
}
// 堆调整方法
public static 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) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// 递归调整堆
heapify(arr, n, largest);
}
}
// 打印数组的方法
public static void printArray(int[] arr) {
for (int value : arr) {
System.out.print(value + " ");
}
System.out.println();
}
}
heapify
方法用于维护堆的性质,确保每个父节点都大于其子节点。堆排序是一种高效的排序算法,适用于大规模数据的排序。它的原地排序特性使得它在内存使用上非常高效。通过理解堆的结构和调整过程,可以更好地掌握堆排序的实现和应用。