java - 基于数组的堆排序中数组索引越界

Question

我正在尝试编写一个基于数组的堆排序算法实现。目标是在数组中构建一个堆，然后删除数组根部的最小元素并将其放回到原始数组中。一直这样做直到数组排序完毕。

根的替换应该来自数组中的最后一个元素，然后将其删除并放入根中。如有必要，新的根元素将与其子元素之一交换。这一直持续到它位于正确的位置

但是我不断收到数组索引越界异常，但我找不到问题所在。我已经为此工作太久了。

如果有人能帮助我，我将非常感激。

public class ImprovedHeapSort<T>
{
    /**
     * @param unsortedArr Array to be sorted
     * @return sortedArr The sorted array
     * 
     * Static method which is an improved version of the HeapSort algorithm. The array 
     * is used to create a sorted array, which is treated as a minheap. 
     * 
     * The root is at index 0 and the last element is at index length-1.
     * Each element is compared to its children, which are at positions 2n+1 and 2(n+1).  
     * Swapping and comparison continues until the root is reached.
     * 
     * 
     */

    public static <T extends Comparable<T>> T[] HeapSort (T[] unsortedArr)
    {
        /*
         * Throw exception if array is empty.
         */
        if (unsortedArr[0] == null)
        {
            throw new EmptyCollectionException("Array");
        }

        /*
         * If array only contains one element.
         */
        if (unsortedArr.length == 1)
        {
            return unsortedArr;
        }



        T[] heapArr = Arrays.copyOf(unsortedArr, unsortedArr.length);


        for(int i = 0; i < unsortedArr.length; i++)
        {

            heapArr[i] = unsortedArr[i];

            /*
             * Swapping to put element in appropriate location, if necessary.
             */

                int cur = i;
                T temp = heapArr[i];

                /*
                 * Swapping until root isn't reached and the element being added
                 * would no longer be less than its parent.
                 */
                while(cur > 0 && temp.compareTo(heapArr[(cur-1)/2]) < 0)
                {
                    heapArr[cur] = heapArr[(cur-1)/2];  //Swap cur with parent
                    cur = (cur-1)/2;                        //Move up to parent

                }

                heapArr[cur] = temp;                        //Insert at appropriate spot.

        }

        /*
         * Remove the root element from the heap array and add it to unsortedArr
         * 
         */




        for (int y = 0; y < unsortedArr.length; y++)
        {   
                int count = heapArr.length - (y+1);     //Count decreased after every pass.
                T rootElem = heapArr[0];                //Store root
                heapArr[0] = heapArr[heapArr.length- (y+1)];    //Set root to last element.
                unsortedArr[y] = rootElem;              //Add root to unsortedArr

                int node = 0;
                int left = 1;
                int right = 2;
                int next;


                if ((heapArr[left] == null) && (heapArr[right] == null))
                    next = count-1;
                else if (heapArr[right] == null)
                    next = left;
                else if (heapArr[left].compareTo(heapArr[right]) < 0)
                    next = left;
                else
                    next = right;

                T temp = heapArr[node];


            /*
             * Swap until appropriate location is found. Least child is shifted up.
             */

            while ((next < count) && 
                (heapArr[next]).compareTo(temp) < 0)
            {
                heapArr[node] = heapArr[next];
                node = next;
                left = 2 * node + 1;
                right = 2 * (node + 1);

                if ((heapArr[left] == null) && (heapArr[right] == null))
                    next = count-2;
                else if (heapArr[right] == null)
                    next = left;
                else if (heapArr[left].compareTo(heapArr[right]) < 0)
                    next = left;
                else
                    next = right;
            }
            heapArr[node] = temp;       //Insert node at appropriate location
        }



        return unsortedArr;

Answer 1

您的代码中有一些边界错误。

首先，让我们看这里:

    /*
     * Throw exception if array is empty.
     */
    if (unsortedArr[0] == null)
    {
        throw new EmptyCollectionException("Array");
    }

如果数组为空，此代码实际上不会引发异常。相反，它会尝试查看索引 0，查看该值是否为 null，如果是，则抛出异常。因此，如果您尝试传入大小为 0 的数组或空数组，您将收到边界错误或空指针异常。要解决此问题，请尝试将其重写为

if (unsortedArr == null) {
    ...
}

您可能不希望在长度为 0 的数组上自动失败。它完全定义了如何对其进行排序:它已经排序了!

此外，我不确定您在这里打算做什么，但我几乎可以肯定这不是您想要的:

            int node = 0;
            int left = 1;
            int right = 2;
            int next;


            if ((heapArr[left] == null) && (heapArr[right] == null))
                next = count-1;
            else if (heapArr[right] == null)
                next = left;
            else if (heapArr[left].compareTo(heapArr[right]) < 0)
                next = left;
            else
                next = right;

请注意，无论数组有多大，node、left 和 right 始终是索引 0、1 和 2。如果您传入一个小数组(例如，大小 2)，这将读取末尾。

展望 future ，我的感觉是您需要更多地学习如何调试程序。当我运行代码时，此处引发的异常将我直接带到导致问题的程序行，从那里就不难找出发生异常的地方。我希望这有助于为您指明正确的方向，祝您好运!