Описание алгоритма:
- Сортируемый массив разбивается на две части примерно одинакового размера.
- Каждая из получившихся частей сортируется отдельно.
- Два получившихся упорядоченных массива соединяются в один. При этом наименьший из первых элементов двух массивов записывается в результирующий массив, и эта операция повторяется, пока не закончатся элементы в этих двух массивах.
Реализуем этот алгоритм на Java.
Внимание! Не следует писать алгоритмы сортировки самостоятельно для реальных приложений. Нужно использовать готовые алгоритмы для коллекций и методы из java.util.Arrays.
Итак, моя реализация сортировки слиянием на Java:
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 |
import java.util.Arrays; /** * Реализация сортировки слиянием на Java * @see https://urvanov.ru * */ public class Main { public static void main(String[] args) { int[] array1 = { 8, 0, -3, 5, 6, 9, 8, -4, 2, -99, 43 }; int[] result = mergesort(array1); System.out.println(Arrays.toString(result)); } public static int[] mergesort(int[] array1) { int[] buffer1 = Arrays.copyOf(array1, array1.length); int[] buffer2 = new int[array1.length]; int[] result = mergesortInner(buffer1, buffer2, 0, array1.length); return result; } /** * * @param buffer1 Массив для сортировки. * @param buffer2 Буфер. Размер должен быть равен размеру buffer1. * @param startIndex Начальный индекс в buffer1 для сортировки. * @param endIndex Конечный индекс в buffer1 для сортировки. * @return */ public static int[] mergesortInner(int[] buffer1, int[] buffer2, int startIndex, int endIndex) { if (startIndex >= endIndex - 1) { return buffer1; } // уже отсортирован. int middle = startIndex + (endIndex - startIndex) / 2; int[] sorted1 = mergesortInner(buffer1, buffer2, startIndex, middle); int[] sorted2 = mergesortInner(buffer1, buffer2, middle, endIndex); // Слияние int index1 = startIndex; int index2 = middle; int destIndex = startIndex; int[] result = sorted1 == buffer1 ? buffer2 : buffer1; while (index1 < middle && index2 < endIndex) { result[destIndex++] = sorted1[index1] < sorted2[index2] ? sorted1[index1++] : sorted2[index2++]; } while (index1 < middle) { result[destIndex++] = sorted1[index1++]; } while (index2 < endIndex) { result[destIndex++] = sorted2[index2++]; } return result; } } |
Достоинства:
- Быстрый. Примерно O(n log n) операций.
- Можно использовать на связанных списках.
- Можно сделать реализацию, использующую параллельные потоки.
- Сохраняет порядок равных элементов (устойчивая)
Недостатки:
- На почти отсортированных массивах работает также, как и на неотсортированных.
- Нужна дополнительная память для буфера.
Вам также может быть интересна быстрая сортировка и сортировка вставками.
Мсье собрался проходить собеседование?
Какие же у тебя крутые статьи)