Heap Sort 堆排序

堆排序（Heap Sort）是一种基于二叉堆数据结构的排序算法，其思路如下：

1. 构建一个最大堆（或最小堆），使得每个节点的值都大于（或小于）其子节点的值。
2. 将堆顶元素与堆的最后一个元素交换，然后将堆的大小减1。
3. 对新的堆顶元素进行下沉操作（调整堆），使得堆重新满足堆的性质。
4. 重复步骤2和步骤3，直到堆的大小为1，排序完成。

以下是堆排序的具体步骤：

1. 构建最大堆：从最后一个非叶子节点开始，对每个节点进行下沉操作，使得整个数组成为一个最大堆。
2. 将堆顶元素与堆的最后一个元素交换，并将堆的大小减1。
3. 对新的堆顶元素进行下沉操作，使得堆重新满足最大堆的性质。
4. 重复步骤2和步骤3，直到堆的大小为1，排序完成。

以下是堆排序的示例代码：

public class Sort {  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);  }  }  private 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 temp = arr[i];  arr[i] = arr[largest];  arr[largest] = temp;  heapify(arr, n, largest);  }  }  public static void main(String[] args) {  int[] array = {5, 2, 8, 12, 1, 6};  heapSort(array);  System.out.println("排序结果：");  for (int num : array) {  System.out.print(num + " ");  }  } }

堆排序的时间复杂度为O(n log n)，无论是最好情况、最坏情况还是平均情况下。

堆排序的空间复杂度为O(1)，因为只需要使用常数级别的额外空间。

堆排序是一种不稳定的排序算法，适用于各种数据规模。