堆排序ArrayIndexOutOfBoundsException

Question

我正在研究堆排序项目，但我不断收到错误

 Exception in thread main Java.lang.ArrayIndexOutOfBoundsException:10
at ReplacementSelection.swap(ReplacementSelection.java:42)
at ReplacementSelection.siftDown(ReplacementSelection.java:69)
at Replacement..

class ReplacementSelection {
    static int[] array = new int[]{ 1,2,3,4,5,6,7,8,9,10 }; 

    public static void sort() {

        System.out.println("before:" + Arrays.toString(array));

        for (int i = array.length/2; i >= 0; i--) {
            siftDown(i);
        }

        int count = array.length-1;
        while (count > 0)
        {
            swap(array[0], array[count]);
            --count;
            siftDown(0);
        }

        System.out.println("after:" + Arrays.toString(array));
    }

    public static void swap(int i, int j) 
    { 
        int tmp; 
        tmp = array[i];  
        array[i] = array[j];  
        array[j] = tmp; 
    }


    public static void siftDown(int index)
    {
        int count = array.length;
        // Left child is at index*2+1. Right child is at index*2+2;
        while (true)
        {
            // first find the largest child
            int largestChild = index*2+1;
            // if left child is larger than count, then done
            if (largestChild >= count)
            {
                break;
            }
            // compare with right child
            if (largestChild+1 < count && array[largestChild] < array[largestChild+1])
            {
                ++largestChild;
            }

            // If item is smaller than the largest child, then swap and continue.
            if (array[index] < array[largestChild])
            {
                swap(array[index], array[largestChild]);
                index = largestChild;
            }
            else
            {
                break;
            }
        }
    }

    public static void main(String[] args){
        ReplacementSelection a = new ReplacementSelection();
        a.sort();
    }
}

Answer 1

您已经编写了一个

swap

方法，该方法将 indices 作为参数。但是，您将数组中这些索引处的值而不是索引本身传递给它：

swap(array[0], array[count]);

和

swap(array[index], array[largestChild]);

---

要修复异常错误，只需将索引传递给方法即可：

swap(0, count);

和

swap(index, largestChild);

Answer 2

正如@Pajacar123提到的，你应该学习使用调试器。

排队

swap(array[index], array[largestChild]);

您正在从表的最后一个索引处的数组传递值（索引 9 值 10）。然后当在方法 sawp 行中时

array[i] = array[j];

j 值为 10，而表的最大索引为 9。这会导致异常。您正在尝试引用不存在的元素。