java - 替换选择排序 :

Question

我正在研究替换选择排序项目，但我不断收到错误 Exception in thread main Java.lang.ArrayIndexOutOfBoundsException:10 at ReplacementSelection.swap(ReplacementSelection.java:42) at ReplacementSelection.siftDown(ReplacementSelection.java:69)更换时..

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方法。但是，您将数组中这些索引处的值而不是索引本身传递给它:

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

和

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

<小时/>

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

swap(0, count);

和

swap(index, largestChild);