堆排序的时间复杂度为nlog(n)
/** * 堆树 * * @author XQC */ public class TreeHeap { public static void main(String[] args) { int[] data = {2, 5, 65, 23, 90, 123, 3}; sortHeap(data); System.out.println(Arrays.toString(data)); } public static void maxHeap(int[] data, int start, int end) { int parent = start; int son = parent * 2 + 1; while (son < end) { int temp = son; // 比较左右节点的大小 if (son + 1 < end && data[son] < data[son + 1]) { temp = son + 1; } // temp 表示较大的那个 if (data[parent] > data[temp]) { return; } else { int t = data[parent]; data[parent] = data[temp]; data[temp] = t; // 继续堆化 parent = temp; son = parent * 2 + 1; } } return; } public static void sortHeap(int[] data) { int len = data.length; for (int i = len / 2 - 1; i >= 0; i--) { maxHeap(data, i, len); } for (int i = len - 1; i > 0; i--) { int temp = data[0]; data[0] = data[i]; data[i] = temp; maxHeap(data, 0, i); } } }