基本介绍
堆排序（Heap Sort）是一种基于堆的排序算法，它利用了堆的性质来进行排序。堆是一个完全二叉树，并且满足堆属性，即每个节点的值都大于或等于（或小于或等于）其子节点的值。
堆排序的基本思想是将待排序的序列构建成一个最大堆（或最小堆），然后将堆顶元素与最后一个元素交换，再对剩余的元素进行调整使其满足堆的性质，重复这个过程直到所有元素都排好序。
具体的堆排序过程如下：
- 构建最大堆：从最后一个非叶子节点开始，依次向上调整每个节点，使得每个节点都满足堆的性质。调整的过程可以使用下沉操作（向下比较并交换）或上浮操作（向上比较并交换）实现。
- 将堆顶元素与最后一个元素交换：交换后，最大元素就位于数组的末尾。
- 调整剩余元素：对除去最后一个元素的剩余部分进行调整，使其满足堆的性质。
- 重复步骤2和步骤3，直到所有元素都排好序。
复杂度分析
时间复杂度： 构建最大堆的时间复杂度为 O(n)。构建最大堆的过程需要从最后一个非叶子节点开始，依次向下进行调整，使得每个节点满足堆的性质。整个过程的时间复杂度是线性的，与待排序序列的长度n成正比。调整堆的时间复杂度为 O(nlogn)。每次调整堆的时间复杂度为O(logn)，总共需要进行n-1次调整。因此，堆排序的时间复杂度为 O(nlogn)。
空间复杂度：堆排序是一种原地排序算法，不需要额外的存储空间来存储临时数据，因此其空间复杂度为 O(1)。在堆排序的过程中，所有操作都是在原数组上进行的，不需要额外的空间来存储中间结果或辅助数据结构。
基于java实现
代码语言：java复制
public class HeapSort {
public void sort(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);
}
}
// 调整堆
void heapify(int arr[], int n, int i) {
int largest = i; // 初始化最大值为根节点
int l = 2 * i 1; // 左子节点
int r = 2 * i 2; // 右子节点
// 如果左子节点大于根节点，更新最大值
if (l < n && arr[l] > arr[largest]) {
largest = l;
}
// 如果右子节点大于当前最大值，更新最大值
if (r < n && arr[r] > arr[largest]) {
largest = r;
}
// 如果最大值不是根节点，交换根节点和最大值的位置，并递归调整堆
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
public static void main(String args[]) {
int arr[] = {12, 11, 13, 5, 6, 7};
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("Sorted array is");
printArray(arr);
}
static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; i ) {
System.out.print(arr[i] " ");
}
System.out.println();
}
}
sort函数用于对输入数组进行堆排序，其时间复杂度为 O(nlogn)。- 使用循环从最后一个非叶子节点开始构建最大堆。
- 在每一轮排序中，我们将当前最大值移动到数组的末尾，并重新调整堆结构，使得剩余元素满足最大堆的性质。这个过程重复进行 n-1 次，直到排序完成。
heapify函数用于调整堆的结构，其时间复杂度为 O(logn)。- 首先找出当前节点、左子节点和右子节点中最大的一个，然后将最大的节点交换到当前节点的位置。
- 如果最大值不是当前节点，我们继续递归调用
heapify函数，对新的子树进行调整。
