堆排序

堆排序是一种高效的排序算法，其时间复杂度为 O(nlogn)，其中 n 是要排序的元素数量。堆排序的核心思想是利用堆这种数据结构来实现排序操作。

算法步骤

1. 将待排序序列构造成一个大顶堆。具体来说，从最后一个非叶子节点开始，对每个非叶子节点进行调整，使其满足大顶堆的性质，即父节点的值大于其左右子节点的值。
2. 依次将堆顶元素（最大值）取出，放到待排序序列的末端，然后对剩余的堆进行调整，使其重新满足大顶堆的性质。
3. 重复步骤 2 直到待排序序列中的所有元素都被取出。

代码实现

下面是使用 Java 实现堆排序的代码：

public 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 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 temp = arr[i];arr[i] = arr[largest];arr[largest] = temp;heapify(arr, n, largest);}
}

使用场景

堆排序适用于需要对大规模数据进行排序的场景，例如排序 10 万个整数。与其他 $O(nlogn)$ 的排序算法（如快速排序）相比，堆排序的优势在于不需要额外的存储空间，而且最坏情况下的时间复杂度也比较稳定。

需要注意的是，堆排序不适用于排序少量数据的场景，因为其时间复杂度常数比较大，不如插入排序、选择排序等简单排序算法。另外，在实际应用中，堆排序的常数因子比较大，常被其他排序算法所取代。