public class HeapSort { public static void main(String[] args) { int a[] = { 3, 5, 1, 4, 7, 8 }; sort(a); System.out.println(Arrays.toString(a)); } private static void sort(int[] a) { // 初始化堆,从第一个非叶子结点开始 for (int i = a.length / 2 - 1; i >= 0; i--) { justHeap(a, i, a.length); } // 交換收尾元素 + 调整堆 for (int i = 0; i < a.length; i++) { int temp = a[0]; a[0] = a[a.length - i - 1]; a[a.length - i - 1] = temp; justHeap(a, 0, a.length - i - 1); } } private static void justHeap(int[] a, int i, int length) { int temp = a[i]; for (int k = 2 * i + 1; k < length; k = 2 * i + 1) { if (k + 1 < length && a[k] < a[k + 1]) // 当前结点的左孩子 小于右孩子,k指向右孩子 k++; if (a[k] > temp) { a[i] = a[k]; i = k; } else break; } a[i] = temp; } }