-
Notifications
You must be signed in to change notification settings - Fork 5
/
HeapSort.java
98 lines (90 loc) · 2.06 KB
/
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
package com.github.junyu.solution.data_structure.sort;
import com.github.junyu.solution.data_structure.heap.MaxHeap;
import com.github.junyu.solution.data_structure.heap.MaxIndexHeap;
import com.github.junyu.solution.data_structure.heap.MaxIndexHeap2;
import com.github.junyu.solution.data_structure.heap.MinIndexHeap;
import java.util.Arrays;
/**
* 堆排序
*
* @author ShaoJunyu
* @version $Id$
* @since 2018/6/24 15:57
*/
public class HeapSort {
// /**
// * 最大堆
// * @param arr
// * @param n
// * @return
// */
// public static int[] sort(int arr[], int n) {
//
// MaxHeap maxHeap = new MaxHeap(n);
// int i = 0;
// while (i < n) {
// maxHeap.insert(arr[i]);
// i++;
// }
//
// int j = n - 1;
// while (j >= 0) {
// arr[j] = maxHeap.remove();
// j--;
// }
// return arr;
// }
// /**
// * 最大索引堆
// * @param arr
// * @param n
// * @return
// */
// public static int[] sort(int arr[], int n) {
//
// MaxIndexHeap maxIndexHeap = new MaxIndexHeap(arr,n);
//
// int j = n - 1;
// while (j >= 0) {
// arr[j] = maxIndexHeap.remove();
// j--;
// }
// return arr;
// }
// /**
// * 最小索引堆
// *
// * @param arr
// * @param n
// * @return
// */
// public static int[] sort(int arr[], int n) {
//
// MinIndexHeap minIndexHeap = new MinIndexHeap(arr, n);
//
// int j = 0;
// while (j < n ) {
// arr[j] = minIndexHeap.remove();
// j++;
// }
// return arr;
// }
//
// public static void main(String[] args) {
// }
/**
* 最大索引堆优化版
* @param arr
* @param n
* @return
*/
public static int[] sort(int arr[], int n) {
MaxIndexHeap2 maxIndexHeap = new MaxIndexHeap2(arr,n);
int j = n - 1;
while (j >= 0) {
arr[j] = maxIndexHeap.remove();
j--;
}
return arr;
}
}