#java #algorithm #data-structures #mergesort
#java #алгоритм #структуры данных #сортировка слиянием
Вопрос:
Пытаюсь реализовать сортировку слиянием в Java. Я перебрал в голове свой код и чувствую, что он должен работать, но, очевидно, я делаю что-то не так. Вот код
public static void mergeSort(int[] input, int start, int end) {
if (end - start < 2)
return;
int mid = (start end) / 2;
mergeSort(input, start, mid);
mergeSort(input, mid 1, end);
merge(input, start, mid, end);
}
public static void merge(int[] input, int start, int mid, int end) {
if (input[mid - 1] <= input[mid])
return;
int i = start;
int j = mid;
int tempIndex = 0;
int[] temp = new int[end - start]; //combined size of both arrays being merged
/*if i is >= mid, then that means the left portion of the array is done being sorted
and vice versa if j >= end. Once this happens, we should be able to
just copy the remaining elements into the temp array
*/
while (i < mid amp;amp; j < end) {
temp[tempIndex ] = (input[i] <= input[j]) ? input[i ] : input[j ];
}
//Copying left over elements in left portion
while (i < mid)
temp[tempIndex ] = input[i ];
//Copying left over elements in right portion
while (j < end)
temp[tempIndex ] = input[j ];
//Copy the sorted temp array into the original array
//This is where I think I must be messing up
for (int k = 0; k < temp.length; k ) {
input[start k] = temp[k];
}
}
Я думаю, что, должно быть, я неправильно копирую временный массив с отсортированными элементами обратно в исходный массив, но я не уверен. Я написал комментарии к своему коду, объясняющие мою логику.
Комментарии:
1. Каков был результат ВАШИХ попыток отладки?
Ответ №1:
Взгляните на следующие изменения:
-
Вычисление mid
int mid = start (end — начало) / 2;
-
Правильное назначение указателей i, j.
int i = начало; int j = середина 1;
-
Правильный размер временного массива.
int [] temp = новый int[end-start 1];
-
Исправлено условие циклов while в коде.
class Solution{ public static void mergeSort(int[] input, int start, int end) { if (end == start ) return; int mid = start (end - start) / 2; mergeSort(input, start, mid); mergeSort(input, mid 1, end); merge(input, start, mid, end); } public static void merge(int[] input, int start, int mid, int end) { // No Need of the under mentioned instruction // if(input[mid-1] <= input[mid]) return; int i = start; int j = mid 1; int tempIndex = 0; int [] temp = new int[end-start 1]; //combined size of both arrays being merged /*if i is >= mid, then that means the left portion of the array is done being sorted and vice versa if j >= end. Once this happens, we should be able to just copy the remaining elements into the temp array */ while(i <= mid amp;amp; j <= end){ temp[tempIndex ] = (input[i] <= input[j]) ? input[i ] : input[j ]; } //Copying left over elements in left portion while(i <= mid) temp[tempIndex ] = input[i ]; //Copying left over elements in right portion while(j <= end) temp[tempIndex ] = input[j ]; //Copy the sorted temp array into the original array //This is where I think I must be messing up for(int k = 0; k < temp.length; k ){ input[start k] = temp[k]; } } public static void main(String[] args){ int[] input = {9,4,6,8,5,7,0,2}; mergeSort(input,0,7); for(int i : input) System.out.println(i); } }
Комментарии:
1. Как получилось, что вы добавили 1 к j и 1 к размеру временного массива?
2. @cris, потому что массив для j начинается с mid 1. если start = 2 и end = 5, то общее количество элементов будет равно 4 (2,3,4,5). Вот почему я добавил 1 к началу — концу.