public class 堆排序 { /** * 第一步: * 先建立大根堆(每一个父节点都比左右子节点大)->(根节点最大) * 从最后一个非叶子节点开始 * 第二部: * 把最后一个叶子节点交换 *第三部: * 写一个方法,用来从上到下重新排列子树 */ public static void main(String[] args) { int[] nums = {1,2,3,4,5};//待排序的数组 sort(nums); System.out.println(Arrays.toString(nums)); } private static void sort(int[] arr){ int lengh = arr.length; /** * 第一步:建立大根堆 */ for (int i = lengh/2-1; i >= 0; i--) { //进入建立大根堆方法 bigRootHeap(arr,i,lengh); } System.out.println(Arrays.toString(arr)); for (int i = lengh-1; i > 0 ; i--) { swap(arr,0,i);//将堆顶元素与末尾元素进行交换 bigRootHeap(arr,0,i);//重新对堆进行调整 } } private static void bigRootHeap(int[] arr,int k,int lengh) { //取出根节点的值 //关键步骤:当交换了位置后,继续调整子节点所在子树 int temp = arr[k]; for (int i = 2*k+1; i < lengh; i=2*i+1) { //求该节点与其左右子树谁大,k就指向谁 if (i+1<lengh && arr[i+1]>arr[i]){ i++; } if (temp<arr[i]){ arr[k] = arr[i]; k=i; }else { break; } } arr[k] = temp; } private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }