Сортировка слиянием — это классический алгоритм сортировки «разделяй и властвуй». Вам никогда не придется писать один, потому что вы будете глупы делать это, когда стандартный библиотечный класс уже сделает это за вас. Но полезно продемонстрировать несколько характеристик методов программирования в Scala. Во-первых, краткий обзор сортировки слиянием. Это алгоритм разделяй и властвуй. Список элементов разделен на меньшие и меньшие списки. Когда список имеет один элемент, он считается отсортированным. Затем он объединяется со списком рядом с ним. Если больше нет списков для объединения, исходный набор данных считается отсортированным. Теперь давайте посмотрим, как это сделать, используя императивный подход в Java.
|
01
02
03
04
05
06
07
08
09
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
|
public void sort(int[] values) { int[] numbers = values; int[] auxillaryNumbers = new int[values.length]; mergesort(numbers, auxillaryNumbers, 0, values.length - 1);}private void mergesort(int [] numbers, int [] auxillaryNumbers, int low, int high) { // Check if low is smaller then high, if not then the array is sorted if (low < high) { // Get the index of the element which is in the middle int middle = low + (high - low) / 2; // Sort the left side of the array mergesort(numbers, auxillaryNumbers, low, middle); // Sort the right side of the array mergesort(numbers, auxillaryNumbers, middle + 1, high); // Combine them both // Alex: the first time we hit this when there is min difference between high and low. merge(numbers, auxillaryNumbers, low, middle, high); }}/** * Merges a[low .. middle] with a[middle..high]. * This method assumes a[low .. middle] and a[middle..high] are sorted. It returns * a[low..high] as an sorted array. */private void merge(int [] a, int[] aux, int low, int middle, int high) { // Copy both parts into the aux array for (int k = low; k <= high; k++) { aux[k] = a[k]; } int i = low, j = middle + 1; for (int k = low; k <= high; k++) { if (i > middle) a[k] = aux[j++]; else if (j > high) a[k] = aux[i++]; else if (aux[j] < aux[i]) a[k] = aux[j++]; else a[k] = aux[i++]; }}public static void main(String args[]){ ... ms.sort(new int[] {5, 3, 1, 17, 2, 8, 19, 11}); ...}} |
Обсуждение …
- Вспомогательный массив используется для достижения сортировки. Элементы для сортировки копируются в нее, а затем сортируются и копируются обратно. Важно, чтобы этот массив создавался только один раз, иначе из-за создания обширного массива может снизиться производительность. Метод слияния не должен создавать вспомогательный массив, однако, поскольку он изменяет объект, это означает, что метод слияния имеет побочные эффекты.
- Производительность сортировки слияния большая (O) равна N log N.
Теперь давайте попробуем решение Scala.
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
|
def mergeSort(xs: List[Int]): List[Int] = { val n = xs.length / 2 if (n == 0) xs else { def merge(xs: List[Int], ys: List[Int]): List[Int] = (xs, ys) match { case(Nil, ys) => ys case(xs, Nil) => xs case(x :: xs1, y :: ys1) => if (x < y) x::merge(xs1, ys) else y :: merge(xs, ys1) } val (left, right) = xs splitAt(n) merge(mergeSort(left), mergeSort(right)) } } |
Ключевые вопросы для обсуждения:
- Это та же самая идея «разделяй и властвуй».
- Функция splitAt используется для разделения данных каждый раз на кортеж. Для каждой рекурсии это будет новый новый кортеж.
- Локальная функция слияния затем используется для выполнения слияния. Локальные функции являются полезной функцией, поскольку они способствуют инкапсуляции и предотвращают раздувание кода.
- Ни функции mergeSort (), ни merge () не имеют побочных эффектов. Они не меняют объект. Они создают (и выбрасывают) объекты.
- Поскольку данные не передаются через итерации слияния, нет необходимости передавать начальные и конечные указатели, которые могут стать очень ошибочными.
- Эта рекурсия слияния использует сопоставление с шаблоном, чтобы получить большой эффект здесь. Мало того, что есть совпадение для списков данных, но когда совпадение происходит, списки данных назначаются переменным:
-
xозначает верхний элемент в левом списке -
xs1остальная часть левого списка -
yозначает верхний элемент в правом списке -
ys1означает остальные данные в правом списке
-
Это позволяет очень легко сравнивать верхние элементы и передавать оставшуюся часть даты для сравнения. Будет ли возможен итеративный подход в Java? Конечно. Но это было бы намного сложнее. У вас нет сопоставления с образцом, и у вас нет толчка, чтобы объявить объекты неизменными, как это делает Scala, заставляя вас делать что-то val или var. В Java всегда было бы легче прочитать код для этой проблемы, если бы он был выполнен в императивном стиле, где объекты меняются в течение итераций цикла. Но Scala функционально-рекурсивный подход может быть довольно аккуратным. Итак, здесь мы видим пример того, как Scala облегчает достижение хорошей, чистой, сжатой рекурсии и делает функциональный подход намного более возможным.