Реализация сортировки слиянием с использованием рекурсии на Java

Введение

Merge Sort - это эффективный и стабильный алгоритм сортировки, который использует метод "Разделяй и властвуй" для сортировки массива. В этом лабораторном задании вы научитесь реализовывать Merge Sort на Java с использованием рекурсивного подхода.

Skills Graph

Создайте метод Merge Sort

Создайте публичный статический метод с именем mergeSort(), имеющий три целочисленных параметра: int arrToSort[], startIdx, endIdx. Необходимо проверить, если длина массива меньше 2, то вернуть. В противном случае вычислить индекс середины массива и разделить массив на левую и правую половины. Левая и правая половины также должны быть разделены рекурсивно. После их разделения необходимо объединить их вместе, чтобы получить отсортированный массив.

public static void mergeSort(int[] arrToSort, int startIdx, int endIdx) {
    if (startIdx >= endIdx) {
        return;
    }

    int midIdx = startIdx + (endIdx - startIdx) / 2;
    mergeSort(arrToSort, startIdx, midIdx);
    mergeSort(arrToSort, midIdx + 1, endIdx);
    merge(arrToSort, startIdx, midIdx, endIdx);
}

Создайте метод Merge

Создайте еще один публичный статический метод с именем merge(), имеющий четыре параметра: int arrToSort[], startIdx, midIdx и endIdx. Необходимо инициализировать левый и правый массивы. Затем необходимо объединить оба массива, сравнивая элементы каждого массива и объединяя их в единый массив.

public static void merge(int[] arrToSort, int startIdx, int midIdx, int endIdx) {
    int[] leftArr = new int[midIdx - startIdx + 1];
    int[] rightArr = new int[endIdx - midIdx];

    for (int i = 0; i < leftArr.length; i++) {
        leftArr[i] = arrToSort[startIdx + i];
    }
    for (int i = 0; i < rightArr.length; i++) {
        rightArr[i] = arrToSort[midIdx + i + 1];
    }

    int leftArrIdx = 0, rightArrIdx = 0, sortedArrIdx = startIdx;
    while ((leftArrIdx < leftArr.length) && (rightArrIdx < rightArr.length)) {
        if (leftArr[leftArrIdx] < rightArr[rightArrIdx]) {
            arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
            leftArrIdx += 1;
        } else {
            arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
            rightArrIdx += 1;
        }
        sortedArrIdx += 1;
    }

    while (leftArrIdx < leftArr.length) {
        arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
        leftArrIdx += 1;
        sortedArrIdx += 1;
    }

    while (rightArrIdx < rightArr.length) {
        arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
        rightArrIdx += 1;
        sortedArrIdx += 1;
    }
}

Тестирование Merge Sort

Протестируем метод mergeSort(), написав код для сортировки входного массива. Создайте метод main. Затем объявите целочисленный массив с несколькими несортированными значениями. Вызовите метод mergeSort() и передайте ему несортированный массив. Наконец, выведите отсортированный массив в консоль. Код для этого шага будет выглядеть так:

public static void main(String[] args) {
    int[] arrToSort = { 4, 2, 8, 0, 1, 6 };
    mergeSort(arrToSort, 0, arrToSort.length - 1);
    System.out.println(Arrays.toString(arrToSort));
}

После запуска программы вывод должен быть: [0, 1, 2, 4, 6, 8].

Тестирование с пустым массивом

Создайте еще один тест для пустого массива. Объявите пустой целочисленный массив. Вызовите метод mergeSort() и передайте ему пустой массив. Наконец, выведите отсортированный массив в консоль. Код для этого шага будет выглядеть так:

int[] emptyArr = {};
mergeSort(emptyArr, 0, emptyArr.length - 1);
System.out.println(Arrays.toString(emptyArr));

Вывод должен быть таким же, как и входной.

Тестирование с массивом из одного элемента

Создайте еще один тест с массивом, содержащим только один элемент. Объявите целочисленный массив из одного элемента. Вызовите метод mergeSort() и передайте ему этот массив. Наконец, выведите отсортированный массив в консоль. Код для этого шага будет выглядеть так:

int[] singleElementArr = {7};
mergeSort(singleElementArr, 0, singleElementArr.length - 1);
System.out.println(Arrays.toString(singleElementArr));

Вывод должен быть таким же, как и входной.

Тестирование с отрицательными значениями

Создайте еще один тест для массива, состоящего из отрицательных целых чисел. Объявите целочисленный массив, который содержит некоторые отрицательные целые числа. Вызовите метод mergeSort() и передайте массив в качестве аргумента. Наконец, выведите отсортированный массив в консоль. Код для этого шага будет выглядеть так:

int[] arrWithNegatives = {-7, 2, -9, 0, -1, 6, 8};
mergeSort(arrWithNegatives, 0, arrWithNegatives.length - 1);
System.out.println(Arrays.toString(arrWithNegatives));

После запуска программы вывод должен быть: [-9, -7, -1, 0, 2, 6, 8].

Тестирование с нечисловыми элементами

Создайте еще один тест, отсортируя массив нечисловых элементов. Объявите массив строк. Вызовите метод mergeSort() и передайте массив в качестве аргумента. Наконец, выведите отсортированный массив в консоль. Код для этого шага будет выглядеть так:

String[] strsToSort = {"John", "David", "Emily", "Bob", "Christine"};
mergeSort(strsToSort, 0, strsToSort.length - 1);
System.out.println(Arrays.toString(strsToSort));

После запуска программы вывод должен быть: ['Bob', 'Christine', 'David', 'Emily', 'John'].

需注意，这里英文原文输出的格式有误，俄文翻译按照正确格式输出了，但实际英文原文中数组元素应该用双引号包裹，即["Bob", "Christine", "David", "Emily", "John"] 。

Финальный исходный код

Вот финальный исходный код для сортировки слиянием (Merge Sort):

import java.util.Arrays;

public class MergeSort {
   public static void mergeSort(int[] arrToSort, int startIdx, int endIdx) {
       if (startIdx >= endIdx) {
           return;
       }

       int midIdx = startIdx + (endIdx - startIdx) / 2;
       mergeSort(arrToSort, startIdx, midIdx);
       mergeSort(arrToSort, midIdx + 1, endIdx);
       merge(arrToSort, startIdx, midIdx, endIdx);
   }

   public static void merge(int[] arrToSort, int startIdx, int midIdx, int endIdx) {
       int[] leftArr = new int[midIdx - startIdx + 1];
       int[] rightArr = new int[endIdx - midIdx];

       for (int i = 0; i < leftArr.length; i++) {
           leftArr[i] = arrToSort[startIdx + i];
       }

       for (int i = 0; i < rightArr.length; i++) {
           rightArr[i] = arrToSort[midIdx + i + 1];
       }

       int leftArrIdx = 0, rightArrIdx = 0, sortedArrIdx = startIdx;
       while ((leftArrIdx < leftArr.length) && (rightArrIdx < rightArr.length)) {
           if (leftArr[leftArrIdx] < rightArr[rightArrIdx]) {
               arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
               leftArrIdx += 1;
           } else {
               arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
               rightArrIdx += 1;
           }
           sortedArrIdx += 1;
       }

       while (leftArrIdx < leftArr.length) {
           arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
           leftArrIdx += 1;
           sortedArrIdx += 1;
       }

       while (rightArrIdx < rightArr.length) {
           arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
           rightArrIdx += 1;
           sortedArrIdx += 1;
       }
   }

   public static void main(String[] args) {
       //create an unsorted integer array
       int[] arrToSort = { 4, 2, 8, 0, 1, 6 };
       //sort the integer array using Merge Sort
       mergeSort(arrToSort, 0, arrToSort.length - 1);
       //print the sorted array
       System.out.println(Arrays.toString(arrToSort));

       //create an empty integer array
       int[] emptyArr = {};
       //sort the empty array
       mergeSort(emptyArr, 0, emptyArr.length - 1);
       //print the sorted array
       System.out.println(Arrays.toString(emptyArr));

       //create a single-element array
       int[] singleElementArr = {7};
       //sort the single-element array
       mergeSort(singleElementArr, 0, singleElementArr.length - 1);
       //print the sorted array
       System.out.println(Arrays.toString(singleElementArr));

       //create a negative integer array
       int[] arrWithNegatives = {-7, 2, -9, 0, -1, 6, 8};
       //sort the negative integer array
       mergeSort(arrWithNegatives, 0, arrWithNegatives.length - 1);
       //print the sorted array
       System.out.println(Arrays.toString(arrWithNegatives));

       //create a string array
       String[] strsToSort = {"John", "David", "Emily", "Bob", "Christine"};
       //sort the string array
       mergeSort(strsToSort, 0, strsToSort.length - 1);
       //print the sorted array
       System.out.println(Arrays.toString(strsToSort));
   }
}

Запустите программу

Скомпилируйте и запустите программу с использованием терминала:

javac MergeSort.java && java MergeSort

Резюме

В этом практическом занятии вы узнали, что такое сортировка слиянием (Merge Sort), как она работает и как реализовать ее на Java. Вы создали два публичных статических метода mergeSort() и merge(), чтобы соответственно разделить и объединить входной массив. После реализации вы проверили ее на различных входных данных, обсудили временную и пространственную сложность и подтвердили ее функциональность. Поздравляем! Вы успешно завершили практическое занятие по сортировке слиянием на Java.