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:
|
import java.util.Arrays;
public class HeapSort {
public static class SortUtil {
public static void vertausche ( int [] a, int x, int st) {
int y = a[x];
a[x]=a[st];
a[st]= y;
}
}
/** Array of int sortieren mittels HeapSort */
public static void sort(int[] daten) {
// Heap erzeugen (Bottom-Up)
for (int i = daten.length / 2 - 1; i >= 0; --i) {
korrigiere(daten, i, daten.length);
}
// Heap auslesen bis er leer ist:
for (int i = daten.length - 1; i > 0; --i) {
SortUtil.vertausche(daten, 0, i);
korrigiere(daten, 0, i);
}
}
/** Heap an der Position i korrigieren */
public static void korrigiere(int[] daten, int i, int len) {
int a = i+1 , g;
while (2*i<= len) {
g=2*a;
if ( g< len)
if ( daten[g-1]>daten[g])
g++;
if ( daten[a-1]> daten[g-1]){
SortUtil.vertausche(daten, a-1, g-1);
g=a;
}
else
break;
}
}
public static void main (String [] args) {
int[] testarray = {7, 9, 5, 6, 4, 0, 1, 1, 9, 8};
sort(testarray);
System.out.println(Arrays.toString(testarray));
}
}
|