Ошибка в рекурсивной селекции?

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

Я протестировал ваш код, и он не сортировался даже после исправления «Исключения из границ».Я изменил ваш метод findBig, чтобы он работал.Принцип таков:

1. Если длина вложенного массива равна единице (начало == конец), то самый большой элемент - массив [начало]
2. , разделите массив пополам
3. Рекурсивно найти индекс самого большого элемента в левой части
4. Рекурсивно найти индекс, если самый большой элемент в правой стороне
5. Сравните самый большой элемент левой стороны с этимправой части массива и возвращает индекс самого большого из них.

Это приводит к следующему коду, который сортирует массив в порядке убывания:

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] + " ");
        }
    }
}

Answer 2

Попробуйте изменить это в своем методе 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.