堆排序（Heap Sort）是一种基于堆数据结构的比较排序算法。堆是一棵完全二叉树，具有堆属性：对于最大堆，每个节点的值都大于或等于其子节点的值；对于最小堆，每个节点的值都小于或等于其子节点的值。堆排序利用了堆的这一特性来实现高效的排序。
堆排序的基本思想
堆排序的基本思想是先将待排序的数组构造成一个最大堆（或最小堆），然后通过不断地取出堆顶元素（最大值或最小值），重建堆，从而完成排序。
堆排序的步骤
- 构建最大堆：
- 从数组的中间开始（即最后一个非叶子节点），向前遍历，将每个节点和其子节点重新排列，使得整个数组符合最大堆的特性。
- 排序：
- 将堆顶元素（最大值）与数组末尾元素交换，这样最大值就放到了最终的位置。
- 将数组长度减 1（排除已经放置到最终位置的元素），重新调整堆，使其再次满足最大堆的特性。
- 重复上述步骤，直到整个数组有序。
代码示例（Java）
代码语言：javascript复制public class HeapSort {
public static void heapSort(int[] array) {
int n = array.length;
// 构建最大堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(array, n, i);
}
// 一个一个从堆顶取出元素，放到已排序区域
for (int i = n - 1; i > 0; i--) {
// 交换当前堆顶元素和当前未排序部分的最后一个元素
swap(array, 0, i);
// 调整剩下的堆，长度减 1
heapify(array, i, 0);
}
}
private static void heapify(int[] array, int n, int i) {
int largest = i; // 假设当前节点 i 是最大值
int left = 2 * i 1; // 左子节点索引
int right = 2 * i 2; // 右子节点索引
// 如果左子节点存在且大于当前节点，则更新 largest
if (left < n && array[left] > array[largest]) {
largest = left;
}
// 如果右子节点存在且大于当前节点，则更新 largest
if (right < n && array[right] > array[largest]) {
largest = right;
}
// 如果 largest 不是当前节点 i，交换它们并继续调整
if (largest != i) {
swap(array, i, largest);
heapify(array, n, largest);
}
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String[] args) {
int[] array = {12, 11, 13, 5, 6, 7};
System.out.println("Original array: ");
printArray(array);
heapSort(array);
System.out.println("Sorted array: ");
printArray(array);
}
private static void printArray(int[] array) {
for (int value : array) {
System.out.print(value " ");
}
System.out.println();
}
}代码解释
- heapSort 方法：这是堆排序的主方法。首先，通过
heapify函数构建最大堆，然后不断将堆顶元素移到数组末尾，调整剩余的堆。 - heapify 方法：调整以
i为根的子树，使其成为最大堆。它检查i节点和其子节点的值，确保最大的值在i位置。如果i位置不是最大值，交换它和最大子节点的位置，并递归调整交换后的子树。 - swap 方法：交换数组中两个元素的位置。
- main 方法：演示如何使用
heapSort方法排序一个整数数组，并打印排序前后的数组。 - printArray 方法：用于打印数组元素。
运行结果
代码语言：javascript复制Original array:
12 11 13 5 6 7
Sorted array:
5 6 7 11 12 13 堆排序的特点
- 时间复杂度：堆排序在最坏、平均和最好情况下的时间复杂度均为 O(nlogn)O(n log n)O(nlogn)。
- 空间复杂度：堆排序的空间复杂度为 O(1)O(1)O(1)，因为它只需要常量级的额外空间。
- 稳定性：堆排序不是稳定的排序算法，因为在排序过程中，元素的相对顺序可能会改变。
总结
堆排序是一种高效的排序算法，尤其适用于大数据量的排序。它利用堆这种数据结构的特点，保证了较好的时间复杂度和低空间消耗。虽然它不如快速排序常用，但在需要稳定的性能和低空间开销时，堆排序是一个不错的选择。
