前言
学习堆排序前，我们需要先对堆有一定的认识和了解，如果你还不了解堆的话，可以先看看我的另外一篇博客《堆的引入与实现》
算法思路
我们先使用堆的上浮使得数组中的数构成大根堆，再使用堆的下沉，就可以得到当前堆中的最大值，并放到下标为 heapSize 的位置，并把 heapSize - 1 , 继续使用堆的下沉，直到heapSize = 0
代码实现
public class heapSort {
public static void main(String[] args) {
int[] arr = new int[]{3, 2, 4, 5, 6, 2, 1, 7, 5};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void heapSort(int[] arr) {
if(arr==null || arr.length < 2) {
return;
}
for (int i =0;i<arr.length;i++){ // O(N)
heapInsert(arr, i); // O(logN)
}
int heapSize = arr.length;
swap(arr, 0, --heapSize);
while (heapSize > 0) { // O(N)
heapify(arr,0, heapSize); // O(logN)
swap(arr, 0, --heapSize); // O(1)
}
}
// 这是关于堆的上浮与下沉的代码，我们在之前的文章已经介绍过
public static void heapInsert(int[] arr, int index) {
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
public static void heapify(int[] arr, int index, int heapSize) {
int left = 2 * index + 1;
while (left < heapSize) {// 表明此时有孩子节点
// 找出左孩子和右孩子中更大的值，
// 如果右孩子存在且右孩子的值大于左孩子，就返回右孩子的下标，否则返回左孩子的下标
int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
// 将孩子中更大的那一个和父亲比较，如果比父亲大，则把下标给 largest
largest = arr[largest] > arr[index] ? largest : index;
// 如果孩子节点都没父亲大，则结束比较
if (largest == index) {
return;
}
swap(arr, index, largest);
// 记录 largest ，用于下一次循环比较
index = largest;
left = 2 * index + 1;
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
运行结果如下：
时间复杂度
由代码可知，堆排序的时间复杂度为 O(NlogN)
小小的优化
对于这段代码 for (int i =0;i<arr.length;i++){ heapInsert(arr, i); }，我们可以做一个进一步的优化
for (int i = arr.length - 1; i >= 0; i--) {
heapify(arr, i, arr.length);
}
原代码中，是进行循环，使得每一个数都进行堆的上浮，做法和之前在讲解堆的时候举的例子是一样的：用户每次给你一个值，你要保证该数存到数组后仍然对应的是一个大根堆；现在我们可以换个思路，因为用户不再是每次给我们一个值，而是我们最开始就得到了完整的数组，就已经组成了一棵二叉树，只是这树还没有构成大根堆而已，我们现在从最后一个元素往前处理
（1）对于一棵树，它的叶子结点是不需要进行堆的下沉（即 heapify）的，因为它们下面没有孩子结点
（2）而对于下面所标出来的子树而言，它们只需要 heapify 一次，就可以使子树成为大根堆
（3）当（2）中的子树也 heapify 过后，对于倒数第二层的元素而言，它也就只要 heapify 一次就可以变成大根堆
（4）同理，这样根节点也只要和它的孩子结点比较一次就可以变成大根堆
由上面步骤，我们可以得到时间复杂度为 O(N) (因为倒着来之后，对每个结点而言，它最多只需要与左右孩子比较，不需要再与孩子的孩子进行比较)
注意，这里是说数组变成堆的时间复杂度由 O(NlogN) 变为了 O(N)，但是堆排序里根据大根堆进行排序的时间复杂度仍然为 O(NlogN)，所以整体的时间复杂度还是 O(NlogN)
稳定性
堆排序是不稳定的排序
举例如下：
对于这样的大根堆，如果我们使堆上浮，去掉里面最大的元素，那么最后一个元素 3 就会跑到根结点的位置，于是两个 3 的相对位置就发生了变化，所以堆排序是不稳定的排序
应用
题目
已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序
思路
假设 k = 6，那就意味着每一个元素的原始位置距离它排好后的位置不超过 6；
（1）我们现在准备一个小根堆，先遍历前七个数，即下标为 0 到 6 的数，那么排完序后，小根堆的最小值就在 0 位置，而这个最小值也是整个数组的最小值；因为每一个元素的原始位置距离它排好后的位置不超过 6，因此下标大于等于 7 的数排完序后都不可能是在 0 位置上，最终在 0 位置上的数的原始位置一定在下标为 0 - 6 的位置上
（2）我们将 0 位置的数弹出，然后将下标为 7 的数加入到小根堆，小根堆再弹出这个最小值，这个最小值就会在下标为 1 的位置
（3）继续将下标为 8 位置的数放入小根堆...周而复始，直到排完所有元素，即可得到有序的数组
代码
我们使用 Java 中的优先队列 PriorityQueue 来实现我们的算法，这个优先队列的本质其实就是堆
我们会用到它的两个方法：add() 添加元素，poll() 返回队首元素，并使队首元素出队列
（关于优先队列 PriorityQueue ，想了解更多的小伙伴可以自行百度一下唷）
public class heapSortApply {
public static void main(String[] args) {
int[] arr = new int[]{2, 1, 4, 3, 6, 5, 8, 7, 10, 9, 11, 12, 14, 13, 12};
sort(arr, 3);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr, int k) {
// k = 0 表明已经排好序
if (k == 0) {
return;
}
// 优先队列，默认为小根堆
PriorityQueue<Integer> heap = new PriorityQueue<>();
// 先将前 k 个数放入堆中
int index = 0;
while (index < Math.min(arr.length, k)) {
heap.add(arr[index++]);
}
int i = 0;
for (; index < arr.length; i++, index++) {
// 弹出对应的元素
arr[i] = heap.poll();
// 将 index 位置的元素放入堆中
heap.add(arr[index]);
}
while (!heap.isEmpty()) {
arr[i++] = heap.poll();
}
}
}
时间复杂度
如果 k = 6，那么每个数字排好的代价为 log 6，所以时间复杂度为 O(Nlog6)，那对于任意的 k ，该算法的时间复杂度为 O(Nlogk)，因为 k 相对数组来说比较小，所以 logk 可忽略不计，算法的时间复杂度可等同于 O(N)
欢迎来逛逛我的博客 mmimo技术小栈