package algorithm.sort;
public class HeapSort {
public static void main(String[] args) {
int[] a = new int[] {5, 3, 7, 2, 1, 4, 9, 8, 6, 1};
sort(a);
print(a);
}
public static void sort(int[] a) {
if (a == null || a.length == 0)
return;
buildMaxHeap(a);
for (int i = a.length - 1; i > 0; i--) {
exchange(a, i, 0);
maxHeapify(a, 0, i);
}
}
private static void buildMaxHeap(int[] a) {
for (int i = a.length / 2 - 1; i >= 0; i--) {
maxHeapify(a, i, a.length);
}
}
private static void maxHeapify(int[] a, int index, int length) {
int largest = index;
int left = left(index);
if (left < length && a[largest] < a[left])
largest = left;
int right = right(index);
if (right < length && a[largest] < a[right])
largest = right;
if (largest == index)
return;
exchange(a, index, largest);
maxHeapify(a, largest, length);
}
private static int left(int index) {
return index * 2 + 1;
}
private static int right(int index) {
return index * 2 + 2;
}
public static void exchange(int[] a, int i1, int i2) {
int tmp = a[i1];
a[i1] = a[i2];
a[i2] = tmp;
}
public static void print(int[] a) {
if (a == null || a.length == 0)
return;
for (int i = 1; i <= a.length; i++) {
System.out.print(a[i - 1] + "\t");
if (i % 5 == 0)
System.out.println();
}
}
}
原文：http://www.cnblogs.com/look4liming/p/3702237.html