-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHeapSort.java
More file actions
100 lines (90 loc) · 3.79 KB
/
Copy pathHeapSort.java
File metadata and controls
100 lines (90 loc) · 3.79 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
package sort;
import org.junit.Test;
import utils.SwapUtil;
import java.util.Arrays;
/**
* @Author: wei1
* @Date: Create in 2018/11/12 20:55
* @Description: 堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，空间复杂度维O(1)
* 它也是不稳定排序。
* 参考：
* https://www.cnblogs.com/chengxiao/p/6129630.html
* https://blog.csdn.net/loveliuzz/article/details/77618530
* <p>
* 时间复杂度
* 堆排序的时间复杂度，主要在初始化堆过程和每次选取最大数后重新建堆的过程；
* 初始化建堆过程时间：
* O(n)
* 推算过程：
* 首先要理解怎么计算这个堆化过程所消耗的时间，可以直接画图去理解；
* 假设高度为k，则从倒数第二层右边的节点开始，这一层的节点都要执行子节点比较然后交换（如果顺序是对的就不用交换）；倒数第三层呢，则会选择其子节点进行比较和交换，如果没交换就可以不用再执行下去了。如果交换了，那么又要选择一支子树进行比较和交换；
* 那么总的时间计算为：s =2^(i -1)*(k -i )；
* 其中 i
* 表示第几层，2^(i -1)表示该层上有多少个元素，(k -i)表示子树上要比较的次数，如果在最差的条件下，就是比较次数后还要交换；因为这个是常数，所以提出来后可以忽略；
* S =2^(k-2)*1+2^(k-3)*2.....+2*(k-2)+2^(0)*(k-1)===>因为叶子层不用交换，
* 所以i从 k-1开始到 1；
* 这个等式求解，我想高中已经会了：等式左右乘上2，然后和原来的等式相减，就变成了：
* S =2^(k -1)+2^(k -2)+2^(k -3).....+2-(k-1)
* 除最后一项外，就是一个等比数列了，直接用求和公式：S =
* {
* a1[1 - (q ^ n)]
* } /(1-q)；
* S =2^k -k -1；又因为k为完全二叉树的深度，
* 所以(2^k) <=n<(2^k -1)，总之可以认为：k =logn （
* 实际计算得到应该是 log(n+1) <k <=logn ）;
* 综上所述得到：S =n -longn -1，所以时间复杂度为：
* O(n)
* 更改堆元素后重建堆时间：
* O(nlogn)
* 推算过程：
* 1、
* 循环 n -1次，每次都是从根节点往下循环查找，
* 所以每一次时间是 logn，总时间：
* logn(n-1) =nlogn -logn ；
* 综上所述：堆排序的时间复杂度为：
* O(nlogn)
* 空间复杂度
* 因为堆排序是就地排序，空间复杂度为常数：
* O(1)
*/
public class HeapSort {
public static void sort(Integer[] nums) {
if (nums == null || nums.length < 2) {
return;
}
//建立大顶堆前 [4, 6, 8, 5, 9]
Integer length = nums.length;
for (Integer i = length / 2 - 1; i >= 0; i--) {
adjustHeap(nums, i, length);
//建立大顶堆后 [9, 6, 8, 5, 4]
}
System.out.println("建堆后：" + Arrays.toString(nums));
//调整堆 有点巧妙
for (Integer i = length - 1; i > 0; i--) {
//将堆顶元素与最后一个元素进行交换，在进行堆的调整
SwapUtil.swap(nums, 0, i);
adjustHeap(nums, 0, i);
}
}
private static void adjustHeap(Integer[] nums, Integer i, Integer length) {
for (Integer j = 2 * i + 1; j < length; j = 2 * i + 1) {
if (j + 1 < length && nums[j] < nums[j + 1]) {
j = j + 1;
}
if (nums[j] > nums[i]) {
// nums[i] = nums[j];
SwapUtil.swap(nums, i, j);
i = j;
} else {
break;
}
}
}
@Test
public void test() {
Integer[] nums = new Integer[]{4, 6, 8, 5, 9};
System.out.println("堆排前：" + Arrays.toString(nums));
sort(nums);
System.out.println("堆排后：" + Arrays.toString(nums));
}
}