Моя программа сортировки слиянием показывает массив вне границ в Java - PullRequest
Новая
       46

Моя программа сортировки слиянием показывает массив вне границ в Java

2 голосов
/ 15 апреля 2020

Я учусь Java, и я делаю эту программу сортировки слиянием, но она выдает исключение ArrayOutOfBound. В чем моя ошибка?

Я также использую этот код на array.length или array.length-1, но оба случая не удаются. Кажется, мой код не принимает длину массива.

// Чтобы разделить массив --- 

void divide(int a[], int lb, int ub) {
    if (lb < ub) {
        int mid = (lb + ub) / 2;
        divide(a, lb, mid);
        divide(a, mid + 1, ub);
        merge(a, lb, mid, ub);
    }
}

// Для печати фактического массива --- 

static void ActualArray(int a[]) {
    System.out.println("----!!!Merge Sort!!!----");
    System.out.println("Your Array is: ");
    for (int i : a) {
        System.out.print(i + " ");
    }
    System.out.println("\n");
}

// Для объединения массива 

void merge(int a[], int lb, int mid, int ub) {
    int i = lb;
    int j = mid + 1;
    int k = lb;
    int b[] = {};
    while (i <= mid && j <= ub) {
        if (a[i] < a[j]) {
            b[k] = a[i];
            i++;
        } else {
            b[k] = a[j];
            j++;
        }
        k++;
    }
    if (i > mid) {
        while (j <= ub) {
            b[k] = a[j];
            j++;
            k++;
        }
    } else {
        while (i <= mid) {
            b[k] = a[i];
            i++;
            k++;
        }
    }
    System.out.println("Your Sorted Array is: ");
    for (int ele : b) {
        System.out.print(ele + " ");
    }
}

// Основной метод 

public static void main(String args[]) {
    int arr[] = { 25, 16, 45, 17, 84, 61 };
    ActualArray(arr);

    MergeSort obj = new MergeSort();
    obj.divide(arr, 0, arr.length - 1);
}

Error Image

1 Ответ

1 голос
/ 15 апреля 2020

В вашем методе merge есть несколько проблем:

  • вы не выделяете временный массив b. Вы должны записать int b[] = new int[ub - lb + 1];
  • , индекс k во временный массив должен быть инициализирован как 0, а не lb.
  • , вам следует скопировать содержимое временного массива обратно a.
  • печать отсортированного среза предназначена только для отладки.

Вот измененная версия: 

void merge(int a[], int lb, int mid, int ub) {
    int b[] = new int[ub - lb + 1];
    int i = lb;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= ub) {
        if (a[i] < a[j]) {
            b[k++] = a[i++];
        } else {
            b[k++] = a[j++];
        }
    }
    // copy the remaining elements from the left part
    while (i <= mid) {
        b[k++] = a[i++];
    }
    // the remaining elements from the right part are already in the proper place
    // copy back the sorted slice into the original array
    for (i = 0; i < k; i++) {
        a[lb + i] = b[i];
    }
}
...