Упражнения на Java: алгоритм сортировки слиянием

Алгоритм сортировки Java: упражнение-4 с решением

Напишите Java-программу для сортировки массива заданных целых чисел с помощью алгоритма сортировки слиянием.

Согласно Википедии «Сортировка слиянием (также обычно пишется слиянием) является алгоритмом сортировки на основе сравнения O (n log n). Большинство реализаций производят стабильную сортировку, что означает, что реализация сохраняет порядок ввода равных элементов в отсортированном выводе. "

Алгоритм:

Концептуально сортировка слиянием работает следующим образом:

• Разделите несортированный список на n подсписков, каждый из которых содержит 1 элемент (список из 1 элемента считается отсортированным).
• Повторно объединяйте подсписки для создания новых отсортированных подсписков, пока не останется только 1 подсписок. Это будет отсортированный список.

Пример сортировки слиянием :

Сортировка слиянием: графическое представление

Пример решения:

Java-код:

import java.util.Arrays;  
class MergeSort
{
    void merge(int nums[], int left, int m, int right)
    {
        int n1 = m - left + 1;
        int n2 = right - m;
 
        int Left_part_arra[] = new int [n1];
        int Right_part_arra[] = new int [n2];
 
        for (int i=0; i<n1; ++i)
            Left_part_arra[i] = nums[left + i];
        for (int j=0; j<n2; ++j)
            Right_part_arra[j] = nums[m + 1+ j];
        int i = 0, j = 0;
 
        int k = left;
        while (i < n1 && j < n2)
        {
            if (Left_part_arra[i] <= Right_part_arra[j])
            {
                nums[k] = Left_part_arra[i];
                i++;
            }
            else
            {
                nums[k] = Right_part_arra[j];
                j++;
            }
            k++;
        }
 
        while (i < n1)
        {
            nums[k] = Left_part_arra[i];
            i++;
            k++;
        }
 
        while (j < n2)
        {
            nums[k] = Right_part_arra[j];
            j++;
            k++;
        }
    }
 
    // merge()
    void sort(int nums[], int left, int right)
    {
        if (left < right)
        {
            // Find the middle point
            int m = (left+right)/2;
 
            // Sort first halve
            sort(nums, left, m);
			// Sort second halve
            sort(nums , m+1, right);
 
            // Merge the sorted halves
            merge(nums, left, m, right);
        }
    }
 
	// Method to test above
    public static void main(String args[])
    {
        MergeSort ob = new MergeSort();
        int nums[] = {7, -5, 3, 2, 1, 0, 45};
        System.out.println("Original Array:");
        System.out.println(Arrays.toString(nums));
        ob.sort(nums, 0, nums.length-1);
         System.out.println("Sorted Array:");
        System.out.println(Arrays.toString(nums));
        }    
    
}

Пример вывода:

 Оригинальный массив:
[7, -5, 3, 2, 1, 0, 45]
Сортированный массив:
[-5, 0, 1, 2, 3, 7, 45]

Блок - схема:

Редактор кода Java:

Внесите свой код и комментарии через Disqus.

Предыдущий: Напишите Java-программу для сортировки массива заданных целых чисел, используя алгоритм сортировки Radix.
Далее: Напишите программу на Java для сортировки массива заданных целых чисел с использованием алгоритма сортировки кучи.