package tree; public class HeapSort { public static void main(String[] args) { int[] arr = {1,2,3,4,5,0,-7,100,-20}; heapSort(arr); for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); } } //处理的思想是 public static void heapSort(int[] arr){ int temp; for (int length = arr.length ; length > 1; length--) { for (int i = length/2 - 1; i >= 0; i--) {//该树下有多少个非叶子节点,然后从下倒上 从右到左的调整树的结构 adjust(arr,i,length); } //在堆顶部获取最大值,和队尾的进行交换,开启下一轮的构建大顶堆 temp = arr[0]; arr[0] = arr[length - 1]; arr[length - 1] = temp; } } public static void adjust(int[] arr, int i, int length){//对i个非叶子节点进行大堆顶调整 int temp = arr[i]; for (int j = 2 * i + 1; j < length; j = j * 2 + 1) { if ((j + 1) < length && arr[j] < arr[j + 1]){ j++; } if (temp < arr[j]){ arr[i] = arr[j]; arr[j] = temp; temp = arr[i]; }else { break; } } } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)