Skip to content

Commit e29049d

Browse files
coderbruiscoderbruis
committed
[U] 更新堆排序算法
1 parent 61a19b4 commit e29049d

5 files changed

Lines changed: 337 additions & 4 deletions

File tree

‎notes/algorithms/堆排序算法.md‎

Lines changed: 234 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -10,15 +10,249 @@
1010
- 空间复杂度：O(1)
1111
- 稳定性：不稳定
1212

13+
> 动画演示
14+
15+
借助动画演示能更好的理解算法原理。
16+
17+
![二叉堆图](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/pictures/heapSort01.git)
18+
19+
![二叉堆图](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/pictures/heapSort02.git)
20+
1321
## 正文
1422

1523
### 1. 借助辅助空间
1624

25+
此方式的排序步骤分为以下两步：
26+
1. heapify对目标数组进行堆化
27+
2. extractMax弹出最大堆堆顶元素，赋值到新数组中
28+
29+
此种堆排序算法
30+
31+
- 平均时间复杂度为：O(NlogN)
32+
- 空间复杂度为：O(N)
33+
34+
```
35+
import java.util.Random;
36+
37+
/**
38+
*
39+
* 借助辅助空间进行堆排序
40+
*
41+
* @author LuoHaiYang
42+
*/
43+
public class HeapSort01 {
44+
45+
/**
46+
* 堆化完后并没有排序完成
47+
* @param arr
48+
*/
49+
private static void heapify(int[] arr) {
50+
int n = arr.length;
51+
for (int i = n/2; i > 0; i--) {
52+
shiftDown(i, n, arr);
53+
}
54+
}
1755
56+
/**
57+
* 获取最大堆中堆顶元素
58+
*/
59+
private static int extractMax(int[] arr) {
60+
int n = arr.length;
61+
int max = arr[0];
62+
swap(arr, 0, --n);
63+
// 让最后一个元素置0
64+
arr[n] = 0;
65+
shiftDown(0, n, arr);
66+
return max;
67+
}
68+
69+
/**
70+
* 下沉操作
71+
* @param k
72+
*/
73+
private static void shiftDown(int k, int n, int[] arr) {
74+
while (k * 2 + 1 < n) {
75+
// 左子树节点
76+
int j = k * 2 + 1;
77+
if (j + 1 < n && arr[j + 1] > arr[j]) {
78+
j++;
79+
}
80+
if (arr[k] >= arr[j]) {
81+
break;
82+
}
83+
swap(arr, k, j);
84+
k = j;
85+
}
86+
}
87+
88+
/**
89+
* 上浮操作
90+
* @param k
91+
*/
92+
private void shiftUp(int k, int[] arr) {
93+
while (k > 0 && arr[(k-1)/ 2] < arr[k]) {
94+
swap(arr, (k-1)/2, k);
95+
k = (k-1)/2;
96+
}
97+
}
98+
99+
private static void swap(int[] arr, int i, int j) {
100+
int tmp = arr[i];
101+
arr[i] = arr[j];
102+
arr[j] = tmp;
103+
}
104+
105+
public static int[] sort(int[] arr) {
106+
int n = arr.length;
107+
heapify(arr);
108+
int[] result = new int[n];
109+
for (int i = 0; i < n; i++) {
110+
result[i] = extractMax(arr);
111+
}
112+
return result;
113+
}
114+
115+
public static void main(String[] args) {
116+
int n = 100;
117+
int[] test = new int[n];
118+
Random random = new Random();
119+
for (int i = 0; i < n; i++) {
120+
test[i] = random.nextInt(1000);
121+
}
122+
123+
sort(test);
124+
125+
// 测试
126+
for (int i = 1; i < n; i++) {
127+
if (test[i-1] < test[i]) {
128+
System.out.println("Error!");
129+
}
130+
}
131+
132+
}
133+
}
134+
```
18135

19136
### 2. 原地堆排序
20137

138+
不借助辅助空间，实现原地堆排序；算法实现步骤为：
139+
140+
1. 对最后一个非叶子节点至堆顶开始进行下沉操作
141+
2. 然后将0~n-1的堆顶元素替换到最后一位，然后n--，再进行下一轮排序
21142

143+
此方式堆排序
144+
145+
- 平均时间复杂度为：O(NlogN)
146+
- 空间复杂度为：O(1)
147+
148+
```
149+
/**
150+
*
151+
* 原地堆排序！ 不需要额外的空间
152+
*
153+
* 这里构造出来的是一个最小堆
154+
*
155+
* @author LuoHaiYang
156+
*/
157+
public class HeapSort02 {
158+
159+
public static void sort(int[] arr) {
160+
int n = arr.length;
161+
162+
// 注意，此时我们的堆是从0开始索引的
163+
// 从(最后一个元素的索引-1)/2开始
164+
// 最后一个元素的索引 = n-1
165+
// 其实这里 i = (n-1) 也行
166+
for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
167+
siftDown2(arr, n, i);
168+
}
169+
170+
// [a.....v,k]
171+
// [.......]k
172+
// [.....] ba
173+
for (int i = n-1; i > 0; i--) {
174+
// 由于上面执行过下沉操作，所以已经是最大堆（但没有排序完）。所以此时swap就将最大值替换到数组末尾。
175+
swap(arr, 0, i);
176+
// 由于siftDown中是判断 2*k+1 < n ，所以就是对n-1进行下沉操作；
177+
siftDown2(arr, i, 0);
178+
}
179+
}
180+
181+
// 下浮
182+
public static void siftDown(int[] arr, int n, int k) {
183+
184+
while (2 * k + 1 < n) {
185+
int j = 2 * k + 1;
186+
if (j + 1 < n && arr[j+1] > arr[j]) {
187+
j += 1;
188+
}
189+
if (arr[k] >= arr[j]) {
190+
break;
191+
}
192+
swap(arr, k, j);
193+
k = j;
194+
}
195+
}
196+
197+
/**
198+
* 优化下沉过程, 不适用swap交换，通过赋值来代替。
199+
*
200+
* @param arr
201+
* @param n
202+
* @param k
203+
*/
204+
private static void siftDown2(int[] arr, int n, int k) {
205+
206+
int e = arr[k];
207+
208+
while (2 * k + 1 < n) {
209+
int j = 2 * k + 1;
210+
if (j + 1 < n && arr[j + 1] > arr[j]) {
211+
j++;
212+
}
213+
214+
if (e >= arr[j]) {
215+
break;
216+
}
217+
// 此时说明arr[j] > arr[k]; 所以让大值上浮;
218+
arr[k] = arr[j];
219+
k = j;
220+
}
221+
// 将最小元素替换到k的位置
222+
arr[k] = e;
223+
}
224+
225+
public static void swap(int[] arr, int i, int j) {
226+
int tmp = arr[i];
227+
arr[i] = arr[j];
228+
arr[j] = tmp;
229+
}
230+
231+
public static void main(String[] args) {
232+
/*
233+
int n = 100;
234+
int[] test = new int[n];
235+
Random random = new Random();
236+
for (int i = 0; i < n; i++) {
237+
test[i] = random.nextInt(1000);
238+
}
239+
*/
240+
int n = 10;
241+
int[] test = {10, 41, 30, 28, 16, 22, 13, 19, 17, 15};
242+
243+
sort(test);
244+
245+
for (int i = 1; i < n; i++) {
246+
if (test[i-1] > test[i]) {
247+
throw new IllegalArgumentException("Error!");
248+
}
249+
}
250+
}
251+
}
252+
```
253+
254+
- 平均时间复杂度：O(NlogN)
255+
- 空间复杂度：O(1)
22256

23257
## 参考
24258

‎notes/pictures/heapSort01.gif‎

1.48 MB
Loading

‎notes/pictures/heapSort02.gif‎

274 KB
Loading

‎src/main/java/com/bruis/algorithminjava/algorithm/sort/HeapSort01.java‎

Lines changed: 101 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,101 @@
1+
package com.bruis.algorithminjava.algorithm.sort;
2+
3+
import java.util.Random;
4+
5+
/**
6+
*
7+
* 借助辅助空间进行堆排序
8+
*
9+
* @author LuoHaiYang
10+
*/
11+
public class HeapSort01 {
12+
13+
/**
14+
* 堆化完后并没有排序完成
15+
* @param arr
16+
*/
17+
private static void heapify(int[] arr) {
18+
int n = arr.length;
19+
for (int i = n/2; i > 0; i--) {
20+
shiftDown(i, n, arr);
21+
}
22+
}
23+
24+
/**
25+
* 获取最大堆中堆顶元素
26+
*/
27+
private static int extractMax(int[] arr) {
28+
int n = arr.length;
29+
int max = arr[0];
30+
swap(arr, 0, --n);
31+
// 让最后一个元素置0
32+
arr[n] = 0;
33+
shiftDown(0, n, arr);
34+
return max;
35+
}
36+
37+
/**
38+
* 下沉操作
39+
* @param k
40+
*/
41+
private static void shiftDown(int k, int n, int[] arr) {
42+
while (k * 2 + 1 < n) {
43+
// 左子树节点
44+
int j = k * 2 + 1;
45+
if (j + 1 < n && arr[j + 1] > arr[j]) {
46+
j++;
47+
}
48+
if (arr[k] >= arr[j]) {
49+
break;
50+
}
51+
swap(arr, k, j);
52+
k = j;
53+
}
54+
}
55+
56+
/**
57+
* 上浮操作
58+
* @param k
59+
*/
60+
private void shiftUp(int k, int[] arr) {
61+
while (k > 0 && arr[(k-1)/ 2] < arr[k]) {
62+
swap(arr, (k-1)/2, k);
63+
k = (k-1)/2;
64+
}
65+
}
66+
67+
private static void swap(int[] arr, int i, int j) {
68+
int tmp = arr[i];
69+
arr[i] = arr[j];
70+
arr[j] = tmp;
71+
}
72+
73+
public static int[] sort(int[] arr) {
74+
int n = arr.length;
75+
heapify(arr);
76+
int[] result = new int[n];
77+
for (int i = 0; i < n; i++) {
78+
result[i] = extractMax(arr);
79+
}
80+
return result;
81+
}
82+
83+
public static void main(String[] args) {
84+
int n = 100;
85+
int[] test = new int[n];
86+
Random random = new Random();
87+
for (int i = 0; i < n; i++) {
88+
test[i] = random.nextInt(1000);
89+
}
90+
91+
sort(test);
92+
93+
// 测试
94+
for (int i = 1; i < n; i++) {
95+
if (test[i-1] < test[i]) {
96+
System.out.println("Error!");
97+
}
98+
}
99+
100+
}
101+
}

src/main/java/com/bruis/algorithminjava/algorithm/sort/HeapSort.java renamed to src/main/java/com/bruis/algorithminjava/algorithm/sort/HeapSort02.java

Lines changed: 2 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,16 +1,14 @@
11
package com.bruis.algorithminjava.algorithm.sort;
22

3-
import java.util.Random;
4-
53
/**
64
*
75
* 原地堆排序！ 不需要额外的空间
86
*
9-
* 这里构造出来的是一个最小堆！！！！ 即数组的值依次递增
7+
* 这里构造出来的是一个最小堆
108
*
119
* @author LuoHaiYang
1210
*/
13-
public class HeapSort {
11+
public class HeapSort02 {
1412

1513
public static void sort(int[] arr) {
1614
int n = arr.length;

0 commit comments

Comments
 (0)