-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHeapSort.java
More file actions
55 lines (48 loc) · 1.38 KB
/
HeapSort.java
File metadata and controls
55 lines (48 loc) · 1.38 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
package sort;
import java.util.Arrays;
/**
* @ProjectName: leetcode
* @Package: sort
* @ClassName: HeadSort
* @Author: markey
* @Description:
* @Date: 2020/3/16 23:05
* @Version: 1.0
*/
public class HeapSort implements Sort{
@Override
public int[] sort(int[] sourceArray) {
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
int len = arr.length;
buildMaxHeap(arr, len);
// 把最大值放到最后一格（最后一格和第一个对调），剩下的重新调整最大堆
for (int i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0, len);
}
return arr;
}
private void buildMaxHeap(int[] arr, int len) {
// 调整除叶子节点外的所有节点，使符合最大堆
for (int i = (int) Math.floor(len / 2); i >=0 ; i--) {
heapify(arr, i, len);
}
}
// 调整最大堆
private void heapify(int[] arr, int i, int len) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, largest, len);
}
}
}