Слияние двух упорядоченных массивов (реализация на Java)

Java   23 февраля 2012  Автор статьи:  

Приведем пример реализации алгоритма слияния двух упорядоченных массивов в один. На входе алгоритм получает два отсортированных массива, которые задаются своим размером и элементами типа int. На выходе алгоритм выводит упорядоченный массив, состоящий из всех элементов двух исходных.

Этот алгоритм является основой для весьма эффективного алгоритма сортировки, который называется сортировка слиянием (merge sort) и имеет алгоритмическую сложность O(n*log(n)). Сложность же алгоритма слияния двух упорядоченных массивов составляет O(n+m), где n и m — соответственно размеры заданных массивов.


import java.io.PrintWriter;
import java.util.Scanner;

public class Solution {
public static void main(String[] args) {
// Для считывания воспользуемся классом Scanner
// Для вывода - классом PrintWriter
Scanner scanner = new Scanner(System.in);
PrintWriter printWriter = new PrintWriter(System.out);

// Считываем размеры массивов,
// который необходимо слить в
// один отсортированный массив
int n = scanner.nextInt();
int m = scanner.nextInt();

// Динамически выделяем память под
// хранение массивов размера n и m
int[] a = new int[n];
int[] b = new int[m];

// Считываем массивы;
// По условию алгоритма они уже
// должны быть отсортированы
for (int i = 0; i < n; i++) { a[i] = scanner.nextInt(); } for (int i = 0; i < m; i++) { b[i] = scanner.nextInt(); } // Динамически выделяем память под // хранение массива, полученного // слиянием двух исходных, его // размер, очевидно, равен n + m int[] result = new int[n + m]; // Заведем два индекса, указывающих // на первый необработанный элемент // первого и второго массивов int i = 0, j = 0; // И заведем индекс массива-результата, // который указывает позицию, которая // будет заполнена на текущем шаге int index = 0; // Будем повторять сравнение элементов // массивов a и b до тех пор, пока // в каждом из них есть хотя бы один // необработанный элемент while (i < n && j < m) { // В соответствии с тем, текущий элемент // какого массива меньше, мы записываем // этот элемент в массив-результат и // обновляем нужный индекс (i или j) if (a[i] < b[j]) { result[index] = a[i]; i++; } else { result[index] = b[j]; j++; } index++; } // После выполнения предыдущего цикла // все элементы одного из массивов будут // обработаны, тогда оставшиеся элементы // другого массива нужно просто дописать // в массив-результат // Заметим, что одно из условий (i < n) // или (j < m) будет гарантированно ложно while (i < n) { result[index] = a[i]; index++; i++; } while (j < m) { result[index] = b[j]; index++; j++; } // Выводим отсортированный массив for (int k = 0; k < n + m; k++) { printWriter.print(result[k] + " "); } // После выполнения программы необходимо закрыть // потоки ввода и вывода scanner.close(); printWriter.close(); } }

Научиться программировать

  • на Delphi

  • на Java

  • на C++