堆排序🌟🌟🌟🌟
今天我们来学习最后一个排序算法——堆排序。
堆排序，顾名思义，其核心在于“堆”这一数据结构的巧妙运用。
如果你还没有看过我们上一篇所讲的 堆，强烈建议你先掌握这种数据结构，掌握之后你才能更好的理解堆排序的高效精妙之处。
堆排序思路
一种最直接的思路是将数组的所有元素加入到最大堆中，之后再不断的删除最大元素，来得到升序排列的数组。
但这种方法无异于是在做一次选择排序。
下面我们来介绍一种经典而又优雅的基于堆结构的排序算法。
堆排序主要分为两个阶段：最大堆的构造阶段和下沉排序阶段。
最大堆的构造阶段
在这个阶段，我们的目的是把原始的数组组织成一个堆结构。
具体是怎么做的？
首先我们要知道数组的每个位置都是子堆的一个根结点，如果某个结点的两个子结点都是堆了，那么在这个结点上进行 sink 操作就可以将以这个结点作为根结点的子堆变成一个堆。
所以我们可以从右往左，从下往上的对节点进行 sink 操作，而且只需要处理数组一半的节点（也就是从最后一个结点的父结点开始操作），因为节点数量为 1 的子堆不需要处理。
for (int i = (N - 1) / 2; i >= 0; i--) {
sink(i, N, nums);
}
下沉排序阶段
类似于选择排序，从堆顶选择最大元素与堆的最后进行交换，同时减少堆的大小，然后对堆顶的元素进行 sink 操作，使堆有序。
while (N > 0) {
swap(nums, 0, N);
N--;
sink(0, N, nums);
}
代码实现
public class Solution {
public int[] sort (int[] nums) {
int N = nums.length - 1;
for (int i = (N - 1) / 2; i >= 0; i--) {
sink(i, N, nums);
}
while (N > 0) {
swap(nums, 0, N);
N--;
sink(0, N, nums);
}
return nums;
}
private void sink (int i, int N, int[] nums) {
while (i * 2 <= N - 1) {
int j = i * 2 + 1;
j = j + 1 <= N && nums[j] < nums[j + 1] ? j + 1 : j;
if (nums[i] > nums[j]) {
break;
}
swap(nums, i, j);
i = j;
}
}
private void swap (int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
时间复杂度
堆排序的时间复杂度为 ${O(NlogN)}$，其中 N 表示待排序元素的个数。
堆排序过程包括两个主要步骤：建堆阶段和下沉排序。
建堆阶段的时间复杂度为 ${O(N)}$，主要涉及将一个无序序列构建成一个堆的过程。
下沉排序的时间复杂度为 ${O(NlogN)}$，主要包括将堆顶元素与堆的最后一个元素交换并调整堆结构的过程。
总体来说，堆排序的时间复杂度为 ${O(NlogN)}$，具有较高的效率。
空间复杂度
堆排序是一个原地排序算法，不需要额外的辅助空间，所有操作都在原数组上进行。
因此空间复杂度为 ${O(1)}$
稳定性
堆排序是一种不稳定的排序算法。
在堆排序中，通过不断交换堆顶元素与最后一个元素并调整堆结构，可能会改变相同元素之间的相对位置，导致排序后相同元素的顺序发生变化。
因此，堆排序不保证相同元素的稳定顺序，是一种不稳定的排序算法。
写在最后
总的来说，堆排序是一种原地、不稳定、时间复杂度为 ${O(NlogN)}$ 的高效排序算法。
到这里我们就把所有的排序算法都学习完了，下篇文章将会带来所有排序算法的总结！