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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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++