Это проблема заполнения пробелов. Я не могу удалить и переписать вещи. То, что я заполнил, это строки после "// TO DO .... и прежде", является / был мой ответ, строка выше, правильная?
Мой вопрос: 1, 2, 3a-dи 4 исправить, и если да, то почему я получаю ошибку переполнения стека.
На данный момент это возвращает ошибку переполнения стека. Мой опыт - половина вводного курса по Java, и теперь я в курсе структур данных и алгоритмов.
Назначение: Сортировка слиянием
Разработка метода сортировки слиянием,который будет сортировать массив целочисленных значений
Существует четыре места, в которые необходимо внести изменения, чтобы правильно выполнить сортировку. Каждое из этих мест помечено документацией → // TO DO (# 1), (# 2), (# 3a-d) и (# 4).
Если вы запустите приложение и введете '8', выходные данные должны быть идентичны перечисленным.
Пример выходных данных:
Пример выходных данных ниже показывает алгоритм MergeSort с журналами отладочных выходных данных, чтобы показать ход выполнения алгоритма:
Тест сортировки слиянием
Введите число целых элементов:
8
Введите 8 целочисленных элементов
Элемент 1: 6
Элемент 2: 5
Элемент 3: 3
Элемент 4: 1
Элемент 5: 7
Элемент 6: 8
Элемент 7: 2
Элемент 8: 4
Сортировка вызова: низкий [0], высокий [4]
Сортировка вызова: низкий [0], высокий [2]
Сортировка вызова: низкий [0], высокий [1]
Сортировка вызова: низкий [1], высокий [2]
Объединение 2 элементов
Текущий массив: 5 6
Сортировка вызовов: низкий [2], высокий [4]
Сортировка вызовов: низкий [2]высокий [3]
сортировка вызовов: низкий [3], высокий [4]
объединение 2 элементов
текущий массив: 1 3
объединение4 элемента
Текущий массив: 1 3 5 6
Сортировка вызовов: низкий [4], высокий [8]
Сортировка вызовов: низкий [4], высокий [6]]
сортировка вызовов: низкий [4], высокий [5]
сортировка вызовов: низкий [5], высокий [6]
объединение 2 элементов
текущий массив: 7 8
сортировка вызовов: низкий [6], высокий [8]
сортировка вызовов: низкий [6], высокий [7]
вызовsort: low [7], high [8]
Объединение 2 элементов
Текущий массив: 2 4
Объединение 4 элементов
Текущий массив: 24 7 8
Объединение 8 элементов
Текущий массив: 1 2 3 4 5 6 7 8
Элементы после сортировки
1 2 3 4 5 67 8
package mergesort;
import java.util.Scanner;
/* Class MergeSort */
public class MergeSort
{
/* Merge Sort function */
public static void sort( int[] array, int low, int high )
{
int diff;
int midpoint;
/* Calculate Difference between low and high */
diff = high-low;
/* Recursion is called until diff is less than or equal to 1 */
/* Return if less than or equal to 1 */
if ( diff <= 1 )
{
return;
}
/* Calculate the midpoint between low and diff */
midpoint = low + diff/2;
// We will call sort recursively here, once for the lower half of the
// provided array and once for the upper half of the array
System.out.printf( "Calling sort: low [%d], high [%d]\n", low, midpoint );
// DO (# 1): сортировка нижней половины массива
sort(array, low, midpoint);
Мой ответ, строка выше, правильно?
System.out.printf( "Calling sort: low [%d], high [%d]\n", midpoint, high );
// TO(# 2): Сортировать верхнюю половину массива
sort(array, high - midpoint, high);
Верен ли мой ответ, строка выше?
// Merge Two Sorted Subarrays
// Create temporary array and temporary variables
int[] temp = new int[diff];
int i = low, j = midpoint;
System.out.printf( "Merging %d Elements\n", diff );
for ( int k = 0; k < diff; k++ )
{
// Fill in temporary array as necessary
if ( i == midpoint )
{
ЧТОБЫ СДЕЛАТЬ (# 3a) Я полностью растерялся, когда речь заходит о том, как эти две вещи объединяются и почему требуется 4 условия. Я бы предпочел закодировать это с нуля.
temp[k] = array[j++];
Был ли мой ответ, строка выше, верна? } в противном случае, если (j == high)
{
// TO (# 3b)
temp[k] = array[i++];
Был ли мой ответ, строка выше, верна?
}
else if ( array[j] < array[i] )
{
// TO DO (# 3c)
temp[k] = array[j++];
Был ли мой ответ, строка выше, верна?
}
else
{
// TO (# 3d)
temp[k] = array[i++];
Был ли мой ответ, строка выше, верна?
}
}
System.out.print( "Current Array: " );
for ( int k=0; k<diff; k++ )
{
// TO DO (# 4): заполнить массив временными элементами массива
array[k] = temp[k];
Был ли мой ответ, строка выше, верна?
System.out.printf( "%d ", array[low+k] );
}
System.out.println();
}
/* Main method */
public static void main(String[] args)
{
Scanner keyboard = new Scanner( System.in );
int elements, lp;
int intArray[] = null;
System.out.println( "Merge Sort Test\n" );
/* Accept number of elements */
System.out.println( "Enter Number of Integer Elements: " );
elements = keyboard.nextInt();
/* Create array of n elements */
intArray = new int[ elements ];
/* Read Elements from the keyboard */
System.out.println( "\nEnter " + elements + " integer elements" );
for ( lp=0; lp<elements; lp++ )
{
System.out.print( "Element " + ( lp+1 ) + ": " );
intArray[lp] = keyboard.nextInt();
}
/* Call method sort */
sort( intArray, 0, elements );
/* Print sorted Array */
System.out.println( "\nElements After Sorting" );
for ( lp=0; lp<elements; lp++ )
{
System.out.print( intArray[lp] + " " );
}
System.out.println();
}
}