/
Code_10_HeapSort.java
146 lines (132 loc) · 4.17 KB
/
Code_10_HeapSort.java
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
package com.nateshao.basic_01_ten_sort;
import java.util.Arrays;
/**
* @date Created by 邵桐杰 on 2021/10/30 16:05
* @微信公众号 千羽的编程时光
* @个人网站 www.nateshao.cn
* @博客 https://nateshao.gitee.io
* @GitHub https://github.com/nateshao
* @Gitee https://gitee.com/nateshao
* Description: 堆排序
*/
public class Code_10_HeapSort {
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 20;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
heapSort(arr1);
comparator(arr2);
if (!isEqual(arr1, arr2)) {
succeed = false;
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
int[] arr = generateRandomArray(maxSize, maxValue);
printArray(arr);
heapSort(arr);
printArray(arr);
}
/**
* 堆排序
* @param arr
*/
public static void heapSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 建立大根堆
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
int size = arr.length;
swap(arr, 0, --size); // 最后一位数,与第一位数交换。 堆大小减1
while (size > 0) {
heapify(arr, 0, size); // 继续调整大根堆
swap(arr, 0, --size); // 继续。最后一位数,与第一位数交换。 堆大小减1
}
}
/**
* 建立大根堆
*
* @param arr
* @param index
*/
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 size) {
int left = index * 2 + 1; // 左孩子。i*2+1 右孩子:left + 1
while (left < size) { // 堆大小
// 左孩子有孩子比较,谁的值大就取谁
int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
// 节点与左右孩子比较,谁大取谁下标
largest = arr[largest] > arr[index] ? largest : index;
// 是我自己,就不用往下执行
if (largest == index) {
break;
}
swap(arr, largest, index); // largest != index
index = largest;
left = index * 2 + 1;
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void comparator(int[] arr) {
Arrays.sort(arr);
}
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
public static boolean isEqual(int[] arr1, int[] arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
return false;
}
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}