Java实现升序/降序堆排序遇问题，求技术指导

你的堆排序代码逻辑框架正确，但核心错误在于heapify过程没有限制有效堆的范围，导致每次交换后，已经排好序的末尾元素被重新纳入堆调整，破坏了排序流程。

具体问题点 #

在升序/降序排序的循环中，你每次将堆顶元素交换到数组末尾后，调用maxheapify或minheapify时，方法内部始终使用array.length作为堆的边界。但实际上，交换到末尾的元素已经是有序的，不应再参与堆调整，堆的有效大小应该随着排序过程逐步缩小。

修复步骤 #

1. 修改heapify方法，增加堆大小参数：给maxheapify和minheapify添加heapSize参数，用来限定当前需要调整的堆的有效范围，替代原来的array.length。
2. 排序循环中传递正确的堆大小：在排序阶段的循环里，调用heapify时传入当前的堆大小（即当前未排序部分的长度）。

修改后的完整代码 #

import java.util.*;

public class heapSort
{
    static int array[];
    public static void main(String[] args)
    {
        createArray();
        int arrayLength = array.length;

        System.out.println("\nBefore sorting:");
        display(array);

        System.out.println("Sorting by heap sort:");
        System.out.println("1. Ascending");
        System.out.println("2. Descending");
        int choice = new Scanner(System.in).nextInt();

        switch(choice)
        {
            case 1:
                // 构建大顶堆
                for(int i = (arrayLength - 2)/2; i >= 0; i--)
                {
                    maxheapify(array, i, arrayLength);
                }

                // 排序：每次将堆顶最大元素移到末尾，缩小堆范围
                for(int i = arrayLength - 1; i >= 0; i--)
                {
                    // 交换堆顶与当前未排序部分的末尾
                    int temp = array[0];
                    array[0] = array[i];
                    array[i] = temp;

                    // 调整剩余元素为大顶堆，此时堆大小为i
                    maxheapify(array, 0, i);
                }
                break;

            case 2:
                // 构建小顶堆
                for(int i = (arrayLength - 2)/2; i >= 0; i--)
                {
                    minheapify(array, i, arrayLength);
                }

                // 排序：每次将堆顶最小元素移到末尾，缩小堆范围
                for(int i = arrayLength - 1; i >= 0; i--)
                {
                    // 交换堆顶与当前未排序部分的末尾
                    int temp = array[0];
                    array[0] = array[i];
                    array[i] = temp;

                    // 调整剩余元素为小顶堆，此时堆大小为i
                    minheapify(array, 0, i);
                }
                break;

            default:
                System.out.println("Invalid input. Program will terminate.");
                break;
        }

        System.out.println("\nAfter sorting:");
        display(array);
    }

    private static void createArray()
    {
        int arrayLength = 8;
        int lowerLimit = 0;
        int upperLimit = 10;
        array = new int[arrayLength];

        // fill the array with random integers
        for(int i = 0; i < arrayLength; i++)
        {
            array[i] = new Random().nextInt(upperLimit) + lowerLimit;
        }
    }


    private static void maxheapify(int[] array, int currentIndex, int heapSize)
    {
        int leftChild = (2 * currentIndex + 1);
        int rightChild = (2 * currentIndex + 2);
        int largestElement = currentIndex;

        // 仅在堆的有效范围内比较子节点
        if(leftChild < heapSize && array[leftChild] > array[largestElement])
            largestElement = leftChild;
        if(rightChild < heapSize && array[rightChild] > array[largestElement])
            largestElement = rightChild;

        if(largestElement != currentIndex)
        {
            int temp = array[currentIndex];
            array[currentIndex] = array[largestElement];
            array[largestElement] = temp;

            // 递归调整受影响的子堆
            maxheapify(array, largestElement, heapSize);
        }
    }

    private static void minheapify(int[] array, int currentIndex, int heapSize)
    {
        int leftChild = (2 * currentIndex + 1);
        int rightChild = (2 * currentIndex + 2);
        int smallestElement = currentIndex;

        // 仅在堆的有效范围内比较子节点
        if(leftChild < heapSize && array[leftChild] < array[smallestElement])
            smallestElement = leftChild;
        if(rightChild < heapSize && array[rightChild] < array[smallestElement])
            smallestElement = rightChild;

        if(smallestElement != currentIndex)
        {
            int temp = array[currentIndex];
            array[currentIndex] = array[smallestElement];
            array[smallestElement] = temp;

            // 递归调整受影响的子堆
            minheapify(array, smallestElement, heapSize);
        }
    }

    private static void display(int[] array)
    {
        System.out.println();
        for(int i = 0; i < array.length; i++)
        {
            System.out.println(array[i]);
        }
    }
}

修复原理 #

• 构建堆阶段：使用整个数组长度作为堆大小，完成大顶堆/小顶堆的初始化。
• 排序阶段：每次交换堆顶元素到数组末尾后，该元素已处于正确的有序位置，后续堆调整仅针对前面未排序的部分（堆大小设为当前的i），避免干扰已排序元素。

内容的提问来源于stack exchange，提问作者Abitatha Roy