Heap Sort 堆排序
堆排序（Heap Sort）是一种基于二叉堆数据结构的排序算法，其思路如下：
- 构建一个最大堆（或最小堆），使得每个节点的值都大于（或小于）其子节点的值。
- 将堆顶元素与堆的最后一个元素交换，然后将堆的大小减1。
- 对新的堆顶元素进行下沉操作（调整堆），使得堆重新满足堆的性质。
- 重复步骤2和步骤3，直到堆的大小为1，排序完成。
以下是堆排序的具体步骤：
- 构建最大堆：从最后一个非叶子节点开始，对每个节点进行下沉操作，使得整个数组成为一个最大堆。
- 将堆顶元素与堆的最后一个元素交换，并将堆的大小减1。
- 对新的堆顶元素进行下沉操作，使得堆重新满足最大堆的性质。
- 重复步骤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)，因为只需要使用常数级别的额外空间。
堆排序是一种不稳定的排序算法，适用于各种数据规模。
