Массив сортировки - Может ли кто-нибудь помочь мне, где я терплю неудачу? - PullRequest
Новая
       32

Массив сортировки - Может ли кто-нибудь помочь мне, где я терплю неудачу?

0 голосов
/ 18 апреля 2020

Мне нужно организовать массив, и я получаю ошибку OutOfBoundException: 

int[] A = {8, 6, 7, 9, 4, 8, 1, 4, 10, 3};
int start = 0;
int end = A.length;
public void insertionSort(int[] A, int start, int end) {
        for (int i = start; i <= end; i++){
          for (int j = i+1; j > start; j--){
            if(A[j] < A[j-1]){
              int k = j-1;
              swap(A, j, k);

Эта функция подкачки - это метод, уже созданный кем-то другим, и он является профессором, поэтому ошибка не идет оттуда. Кто-нибудь может указать, где я терплю неудачу?

Ответы [ 3 ]

0 голосов
/ 18 апреля 2020

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

for (int i = start; i <= end; i++)

Причина очевидна из следующей строки кода: 

for (int j = i+1; j > start; j--)

В этой строке вы инициализируете j с i + 1 и последующей попыткой доступа к A[j] в следующей строке.

Когда i станет равным end (поскольку вы записали условие завершения как i <= end) j будет равно end + 1, т. Е. В случае вашего массива j будет равно 10 + 1 = 11. Однако последний индекс в A[] равен 9, так как вы уже должны знать, что индекс массива начинается с 0. Всякий раз, когда вы пытаетесь получить доступ к элементу массива из индекса после последнего индекса, выдается ArrayIndexOutOfBoundsException .

Ниже приведен исправленный код: 

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        int[] A = { 8, 6, 7, 9, 4, 8, 1, 4, 10, 3 };
        int start = 0;
        int end = A.length;
        insertionSort(A, start, end);
        System.out.println(Arrays.toString(A));
    }

    static void insertionSort(int[] A, int start, int end) {
        for (int i = start; i < end - 1; i++) {
            for (int j = i + 1; j > start; j--) {
                if (A[j] < A[j - 1]) {
                    int k = j - 1;
                    swap(A, j, k);
                }
            }
        }
    }

    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Выход: 

[1, 3, 4, 4, 6, 7, 8, 8, 9, 10]
0 голосов
/ 19 апреля 2020

Вы действительно близки, и, как я вижу, вы сделали только одну ошибку.

Вот ваш код. 

public void insertionSort(int[] A, int start, int end) {
   for (int j = i+1; j > start; j--){
      if(A[j] < A[j-1]){
         int k = j-1;
         swap(A, j, k);
       }
   }
}

Проблема с внешним for l oop.

Измените его с 

for (int i = start; i <= end; i++)

на 

for (int i = start; i < end-1; i++)

Причины следующие:

  • i <= end будет включать значение end, но поскольку массивы основаны на 0, вы будете на go превышать размер массива.
  • Кроме того, поскольку внутренний l oop добавляет 1 к i, вам необходимо сделать end-1, чтобы i также не превышал размер массива.
0 голосов
/ 18 апреля 2020

Массив начинается с индекса 0, а не 1. Таким образом, длина вашего массива уже вышла за пределы индекса. Просто измените свой первый на l oop, чтобы он работал до тех пор, пока i<end решит вашу проблему. 

for (int i = start; i < end; i++)

Кроме того, ваш внутренний l oop также неверен. Вы можете выбрать, хотите ли вы проверить следующий индекс (i + 1) или предыдущий индекс (i-1). В случае (i + 1) внешний l oop снова заходит слишком далеко (теперь он должен быть i < end-1). Если вы хотите изменить предыдущий индекс (i-1), ваш i должен начинаться с 1, а не с 0.

Например (для замены следующего элемента): 

for (int i = 0; i < end-1; i++){
    for (int j = i+1; j > 0; j--){
        if(A[j] < A[j-1]){
...