创建大根堆
static void buildBigHeap(int[] array, int last) {
//从最大的非叶子节点开始（last - 1 /2）,到根节点终止
for (int i = (last -1) / 2; i >= 0; i--) {
int k = i;
//判断是否超过数组界限，第一轮比较完，该子节点作为父节点时是否为最大值情况
while ((2 * k) + 1 <= last){
//记录最大值的下标
int bigIndex = 2*k+1;
//判断是否右子节点，如果相等无右子节点。小于则右
if(bigIndex < last){
//判断左右子节点的大小
if(array[bigIndex] < array[bigIndex + 1]){
bigIndex++;
}
}
//最大子节点和父节点比较
if(array[k] < array[bigIndex]){
MyUtil.swap(array,k,bigIndex);
System.out.println(Arrays.toString(array)+"有交换"+ "\t" +"父节点 = " + k + "\t" + "最大子节点 = " + bigIndex);
k = bigIndex;
}
else {
System.out.println(Arrays.toString(array)+"无交换");
break;
}
}
}
}
创建大根堆思路
首先找到最后的父节点 ，从下标0开始所以为int last = (array.length -1 -1 )/2 所以父节点一共有0 到 last 个 记录一下当前父节点的下标 以左子节点来判断是否超过数组界限 找出左右子节点的最大值 然后和父节点的值进行比较 交换位置
大根堆排序code
public static void headSort(int[] nums){
System.out.println("原始数组 =" + Arrays.toString(nums));
System.out.println("-----------------------------------");
for(int i = nums.length - 1 ; i > 0; i--){
buildBigHeap(nums, i);
MyUtil.swap(nums, i , 0);
}
}
思路
每次都将前面的值放到最后 因为每次放完后在进行大根堆重组的时候，重组数组大小减1，所以 9 8 7 6 5 4 3 2 1 的顺序排成从小到大
测试code
public static void main(String[] args){
int[] array = MyUtil.createArray();
int[] arrays = new int[array.length];
System.arraycopy(array,0,arrays,0,array.length);
//系统排序
Arrays.sort(arrays);
//堆排序
HeapSort.headSort(array);
boolean compare = MyUtil.compare(array,arrays);
System.out.println(compare);
}
