大根堆创建于排序

    xiaoxiao2022-07-12  150

    创建大根堆

    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); }
    最新回复(0)