在Java中实现堆排序时遇到的问题

Question

我编写了以下程序来在Java中实现堆排序（升序和降序）。其实有以下步骤。

1. 创建一个预先指定大小的数组并使用随机整数初始化它。
2. 将其转换为堆。
3. 排序。

但是，尽管我认为我的代码在逻辑上是正确的，但我无法产生预期的结果。感谢任何形式的帮助或指导。

import java.util.*;

public class heapSort
{
    static int array[];
    public static void main(String[] args)
    {
        // int[] array = new int[1];

        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);
                }

                for(int i = arrayLength - 1; i >= 0; i--)
                {
                    // swap/delete operation
                    int temp = array[0];
                    array[0] = array[i];
                    array[i] = temp;

                    maxheapify(array, 0);
                }
                break;

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

                for(int i = arrayLength - 1; i >= 0; i--)
                {
                    // swap/delete operation
                    int temp = array[0];
                    array[0] = array[i];
                    array[i] = temp;

                    minheapify(array, 0);
                }
                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 leftChild = (2 * currentIndex + 1);
        int rightChild = (2 * currentIndex + 2);
        int largestElement = currentIndex;
        int arrayLength = array.length;

        if(leftChild < arrayLength && array[leftChild] > array[largestElement])
            largestElement = leftChild;
        if(rightChild < arrayLength && array[rightChild] > array[largestElement])
            largestElement = rightChild;

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

            // recursive call
            maxheapify(array, largestElement);
        }
    }

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

        if(leftChild < arrayLength && array[leftChild] < array[smallestElement])
            smallestElement = leftChild;
        if(rightChild < arrayLength && array[rightChild] < array[smallestElement])
            smallestElement = rightChild;

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

            // recursive call
            minheapify(array, smallestElement);
        }
    }

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

我期望最终得到一个排序数组，但它没有产生这个结果。

Answer 1

在堆排序的正确实现中，数组左侧的堆部分会变小，而右侧的已排序部分会增长，直到占据整个数组。您的代码中的问题是您没有减少堆部分。每当您调用 heapify 函数时，它都会将整个数组视为堆。这是错误的，因为值会流入非堆部分，从而造成严重破坏。

因此，在您的

maxheapify

函数中提供一个额外的参数，称为

arrayLength

（替换您已经在那里声明的局部变量），并在交换循环中将

i

的值传递给它。

以下是案例 1 的相关更改：

            case 1:
                for(int i = (arrayLength - 2)/2; i >= 0; i--)
                {
                    maxheapify(array, i, arrayLength); // add argument
                }
                for(int i = arrayLength - 1; i >= 0; i--)
                {
                    // swap/delete operation
                    int temp = array[0];
                    array[0] = array[i];
                    array[i] = temp;

                    maxheapify(array, 0, i); // add argument
                }

...和

maxheapify

功能：

    private static void maxheapify(int[] array, int currentIndex, int arrayLength) // parameter
    {
        int leftChild = (2 * currentIndex + 1);
        int rightChild = (2 * currentIndex + 2);
        int largestElement = currentIndex;
        //int arrayLength = array.length;   *** removed

        if(leftChild < arrayLength && array[leftChild] > array[largestElement])
            largestElement = leftChild;
        if(rightChild < arrayLength && array[rightChild] > array[largestElement])
            largestElement = rightChild;

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

            // recursive call
            maxheapify(array, largestElement, arrayLength); // Added argument
        }
    }