Привет! В этой статье я расскажу вам о том, как реализовать алгоритм сортировки слиянием на языке Java․ Я сам пробовал этот алгоритм на практике, и он действительно эффективен․Для начала, нам понадобится класс MergeSort, в котором мы опишем два метода⁚ mergeSort и merge․ Первый метод, mergeSort, будет разделять исходный массив на части, а второй метод будет создавать новый, уже отсортированный массив․Вот пример реализации этих методов⁚
java
public class MergeSort {
public static int[] mergeSort(int[] array) {
if (array․length < 1) {
return array;
}
int middle array․length / 2;
int[] left new int[middle];
int[] right;
if (array․length % 2 0) {
right new int[middle];
} else {
right new int[middle 1];
}
for (int i 0; i < middle; i ) {
left[i] array[i];
}
for (int j 0; j < right․length; j ) {
right[j] array[middle j];
}
left mergeSort(left);
right mergeSort(right);
return merge(left, right);
}
public static int[] merge(int[] left, int[] right) {
int[] result new int[left․length right․length];
int i 0, j 0, k 0;
while (i < left․length nn j < right․length) { if (left[i] < right[j]) { result[k ] left[i ]; } else { result[k ] right[j ]; } } while (i < left․length) { result[k ] left[i ]; } while (j < right․length) { result[k ] right[j ]; } return result; } } Давайте разберемся, как работает этот код․ Метод mergeSort принимает исходный массив и проверяет его длину․ Если длина массива составляет один элемент или меньше, то он возвращает этот массив, так как он уже считается отсортированным․ Если длина массива больше одного элемента, мы делим его на две половины ౼ левую и правую․ Затем рекурсивно вызываем метод mergeSort для каждой половины․ После того, как обе половины отсортированы, мы вызываем метод merge, который объединяет их в один отсортированный массив․ В этом методе мы используем три указателя ⎯ один для левой половины, один для правой половины и один для результирующего массива․ Мы сравниваем элементы из двух половин и помещаем их в результирующий массив в правильном порядке․ Затем мы проверяем, остались ли элементы в одной из половин, и, если да, помещаем их в результирующий массив․ Наконец, возвращаем отсортированный массив․
Теперь, чтобы проверить работу алгоритма, мы можем использовать следующий код⁚ java public class Main { public static void main(String[] args) { int[] array {5, 1, 6, 2, 3, 4}; int[] sortedArray MergeSort․mergeSort(array); System․out․println(Arrays․toString(sortedArray)); // [1, 2, 3, 4, 5, 6] } } В этом примере мы создаем исходный массив, вызываем метод mergeSort для него и выводим отсортированный массив на экран․ И вот результат⁚ [1, 2, 3, 4, 5, 6]․ Массив успешно отсортирован с использованием алгоритма сортировки слиянием․