堆排序java实现

堆排序就是一种特殊的选择排序，借助顺序二叉树大顶堆/小顶堆的特性，每次将根节点与末尾节点交换值，再将出末尾节点之外的节点重新构造大顶堆/小顶堆，直到未排序的数为1(该值为最大/最小值)时结束排序。

public class HeapSort { public static void main(String[] args) { int[] arr = {4,6,8,5,9,-12,1,-895,1000}; headSort(arr); System.out.println(Arrays.toString(arr)); } public static void headSort(int[] arr) { int temp; //讲顺序二叉树调整为一个大顶堆 for (int i = arr.length/2 -1; i >= 0; i--) { getBigHeap(arr,i,arr.length); } //排序，每次将队首(最大值)放到队尾 for (int j = arr.length-1; j > 0 ; j--) { temp = arr[j]; arr[j] = arr[0]; arr[0] = temp; //再次调整为大顶堆结构 //此时因为是在原有的大顶堆的基础上进行调整的 //所以每次只需调整索引0的位置即可 getBigHeap(arr,0,j); } } public static void getBigHeap(int[] arr,int index,int len) { int temp = arr[index]; //从该非叶子节点的左孩子开始遍历 for (int i = 2*index+1; i < len; i = 2*i+1) { //比较左右节点的大小 if (i+1arr[i]){ i++; } //比较该非叶子节点的值与其左右孩子的大小 // 若小于，则赋值，并将索引定位到其子节点进行下一轮调整 // 若大于，则直接结束循环——原因:每次传入的索引均为未调整过的首个非叶子节点，大于则说明该索引对应的值大于其子树的所有值，无需再进行遍历 if(arr[i] > temp) { arr[index] = arr[i]; index = i; }else { break; } } //for循环结束后，参数中的index已经是该子树中的最大值 //需要将其原来的值赋值给其子节点。 arr[index] = temp; }}