递归选择排序中的错误？

Question

我试图在 java 中递归地实现选择排序，但我的程序一直抛出 ArrayIndexOutOfBounds 异常。不确定我做错了什么。递归对我来说很难。请帮忙！我是初学者。

public static int[] selection(int[] array) {
    return sRec(array, array.length - 1, 0);
}
private static int[] sRec(int[] array, int length, int current) {
    if (length == current) { //last index of array = index we are at
        return array; //it's sorted
    }
    else {
            int index = findBig(array, length, current, 0);
            int[] swapped = swap(array, index, length - current);
            return sRec(swapped, length - 1, current);
    }
}

private static int[] swap(int[] array, int index, int lastPos) {
    int temp = array[lastPos];
    array[lastPos] = array[index];
    array[index] = array[temp];
    return array;
}

private static int findBig(int[] array, int length, int current, int biggestIndex) {
    if (length  == current) {
        return biggestIndex;
    }
    else if (array[biggestIndex] < array[current]) {
        return findBig(array, length, current + 1, current);
    }
    else {
        return findBig(array, length, current + 1, biggestIndex);
    }
}

public static void main (String [] args) {
    int[] array = {8,3,5,1,3};
    int[] sorted = selection(array);
    for (int i = 0; i < sorted.length; i++) {
        System.out.print(sorted[i] + " ");
    }
}

Answer 1

尝试在您的 Swap 方法中更改它：

int temp = array[lastPos];
array[lastPos] = array[index];
array[index] = array[temp];
return array;

对此：

int temp = array[lastPos];
array[lastPos] = array[index];
array[index] = temp;
return array;

您已经获得了要分配给数组的值，当您将其添加到数组时，它会在特定索引中搜索，

例如：

您想在数组中输入值 8

而不是

array[index] = 8

你在做

array[index] = array[8]

那是导致您的 OutOfBounds 异常的原因。

Answer 2

我测试了你的代码，即使修复了 "Out Of bound Exception"，它也没有排序。我已经更改了您的方法 findbig 以使其工作。原则是：

如果子数组的长度为1(begin==end)则最大元素为array[begin]
将数组除以一半
递归求左边最大元素的索引
如果最大的元素在右侧，则递归查找索引
比较数组左边和右边的最大元素，return两者最大的索引。

这导致以下代码按降序对数组进行排序：

public class Sort {

   public static int[] selection(int[] array) {
        return sRec(array,0);
    }
    private static int[] sRec(int[] array, int current) {
      if (current == array.length-1) { //last index of array = index we are at
            return array; //it's sorted
        }
        else {
                int indexOfBiggest = findBig(array, current,array.length-1);
                int[] swapped = swap(array, indexOfBiggest, current );
                return sRec(swapped, current+1);
        }
    }

    private static int[] swap(int[] array, int index, int lastPos) {
        int temp = array[lastPos];
        array[lastPos] = array[index];
        array[index] = temp;
        return array;
    }

    private static int findBig(int[] array, int begin, int end) {
        if (begin < end) {
            int middle = (begin+end)/2;
            int biggestLeft = findBig(array,begin,middle);
            int biggestRight = findBig(array,middle+1,end);
            if(array[biggestLeft] > array[biggestRight]) {
                return biggestLeft;
            }else {
                return biggestRight;
            }
        }else {
            return begin;
        }
     }

    public static void main (String [] args) {
        int[] array = {8,3,5,1,3};
       // System.out.println(findBig(array,0,array.length-1));
        int[] sorted = selection(array);
        for (int i = 0; i < sorted.length; i++) {
            System.out.print(sorted[i] + " ");
        }
    }
}

递归选择排序中的错误？

Bug in recursive selection sort?

java

sorting

recursion

selection-sort