Главная » Java, Структуры данных и алгоритмы » Реализация сортировки методом слияния

0

Во фрагменте кода 10.2 приведена Java-реализация алгоритма сортировки методом слияния. Метод mergeSort является рекурсивным и вызывает метод merge для слияния. Компаратор (см. п. 7.1.4) используется для определения относительного порядка двух элементов в методе merge.

В этой реализации исходная последовательность S и вспомогательные последовательности S\ и S2 модифицируются в результате вводов и удалений только с головы и хвоста. То есть каждая модификация в последовательности, реализованной двусвязным списком или с помощью цикличного массива, занимает 0(1) времени (см. табл. 5.4). В данном случае речь идет о классе NodeSequence (см. фрагмент кода 5.12), используемом для вспомогательных последовательностей.

Следовательно, для последовательности S размером п метод mergeSort(^c) выполняется за время 0(п log п) при условии, что соблюдаются следующие ограничения:

1)    последовательность S реализована двусвязным списком или циклическим массивом;

2)       компаратор с может сравнивать два элемента из Sза 0(1) времени.

!**

*                    Сортирует элементы последовательности S в неубывающем порядке

*                    с помощью компаратора с, пользуясь алгоритмом сортировки слиянием.

*7

public static void mergeSort (Sequence S, Comparator c) { int n = S.size();

// последовательность с 0 и 1 элементом уже упорядочена if (п < 2) return; // разделить int i = n;

Sequence S1 = new NodeSequence(); do { // перемещение первых n/2 элементов в S1 S1 .insertLast(S.remove(S.first()));

i———————— ;

} while (i > n/2);

Sequence S2 = new NodeSequence();

do { // перемещение остальных n/2 элементов в S2 S2.insertLast(S.remove(S.first()));

} while (i > 0); // последовательность S теперь пуста

// рекурсия

mergeSort(S1,c);

mergeSort(S2,c);

// слияние

merge(Sl,S2,c,S);

*                                 Объединить две сортированные последовательности S1 и S2

*                                 в сортированную S.

public static void merge(Sequence S1, Sequence S2, Comparator c, Sequence S) {

while(!S1.isEmptyO && !S2.isEmpty())

if(c.isLessThanOrEqualTo(S1.first().element(), S2.first().element()))

S.insertLast(S1 .remove(S1 .first())); else

S.insertLast(S2.remove(S2.fjrst())); wlrile(!S1.isEmptyO) // перемещение элементов из S1

S.insertLast(S1 .remove(S1 .first())); while(!S2.isEmptyO) // перемещение элементов из S2 S.insertLast(S2.remove(S2.first()));

}

где b > 1 и с > 1 — константы. Такая функция называется рекуррентной, поскольку содержится в обеих частях уравнения. Хотя такое описание

Фрагмент кода 10.2. Методы mergeSort и merge, реализующие алгоритм сортировки слиянием

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии