Упражнения на 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 [] = новый int [n1];  int Right_part_arra [] = новый int [n2];  для (int i = 0; i  

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

 Исходный массив: [7, -5, 3, 2, 1, 0, 45] Сортированный массив  : [- 5, 0, 1, 2, 3, 7, 45] 

Блок-схема:

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

Оцените статью
nanomode.ru
Добавить комментарий