十大经典排序(七)--堆排序
堆排序思路：
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
算法步骤：
创建一个堆 H[0……n-1]（大顶或者小顶），这里咱们构建大顶堆；
把堆首（最大值）和堆尾互换；
将堆的大小减 1，并对堆进行调整，目的是把新的数组顶端数据调整到相应位置；
重复步骤 2，直到堆的尺寸为 1。
题外话：小顶堆和大顶堆构建及维护代码基本一致，这里偷波懒，就不实现了，其实在Java中也有一些原生的类使用堆来实现的，如 PriorityQueue就是个基于优先级堆实现的优先级队列，有兴趣的同学可以看看
代码：
1private static void sort(int arr[]) {
2 if (arr == null || arr.length == 0) {
3 return;
4 }
5
6 int len = arr.length;
7 //构建堆的时候记得 得从下至上
8 for (int i = len - 1; i >= 0; i--) {
9 adj(arr, i, len);
10 }
11 for (int i = len - 1; i > 0; i--) {
12 //交换
13 swap(arr, 0, i);
14 len--;
15 //调整堆
16 adj(arr, 0, len);
17 }
18}
19
20//构建&调整堆
21private static void adj(int arr[], int i, int len) {
22 //保留原始值
23 int temp = arr[i];
24 //假设数组中用 i 为父节点
25 // 那么左子节点的下标就是 2 * i + 1
26 //右子节点下标就是 2 * i + 2
27 for (int k = 2 * i + 1; k < len; k = 2 * k + 1) {
28 //找到左右子节点中最大的那个
29 if (k + 1 < len && arr[k] < arr[k + 1]) {
30 k++;
31 }
32 //如果子节点中有比父节点大的，进行值交换
33 if (arr[k] > temp) {
34 arr[i] = arr[k];
35 //注意 i 的替换
36 i = k;
37 }
38 }
39 arr[i] = temp;
40}
41
42//交换 这里没有采用额外变量，和异或法原理类似
43//有兴趣同学可以试试异或法
44private static void swap(int[] arr, int i, int j) {
45 arr[i] = arr[i] + arr[j];
46 arr[j] = arr[i] - arr[j];
47 arr[i] = arr[i] - arr[j];
48}
时间复杂度：O(nlogn)
空间复杂度：O(1)
以上仅是个人思路解法，觉得还不错欢迎点赞关注分享
往期精彩推荐