Как реализовать этот известный алгоритм
Чтобы описать сортировку слиянием, давайте просто аналогию.
Предположим, у вас есть кусок лего, который вы можете разобрать. Каждая часть имеет свои собственные номера, и вы продолжаете ломать и ломать, пока не будет одна часть друг друга со своими номерами.
Вот схема, показывающая, как это будет выглядеть:
Чтобы понять сортировку слиянием, вы должны помнить несколько следующих вещей:
- Сортировка слиянием
- сливаться
Вот шаги, которые необходимо выполнить:
- Шаг 1. Создайте функцию с именем mergeSort.
- Шаг 2. В методе mergeSort создайте левый и правый подмассивы, возьмите первую половину элементов и скопируйте ее в левый подмассив. Скопируйте вторую половину элементов в правый подмассив.
- Шаг 3. Рекурсивно вызовите сортировку слиянием с левым подмассивом (сама функция).
- Шаг 4. Рекурсивно вызовите сортировку слиянием с правым подмассивом (сама функция)
- Шаг 5: вызовите слияние с левым подмассивом, правым подмассивом, самим исходным массивом, с размером левого массива и размером правого массива.
В функции слияния вы будете сравнивать элементы в левом и правом подмассивах с i и j в качестве индексов для отслеживания текущего элемента, который будет сравниваться в каждом массиве соответственно.
i и j начинаются с 0. У вас также есть еще один индекс, k, который используется для отслеживания самого последнего индекса, в который мы перемещаем новые элементы. Если текущий left_arr[i] < right_arr[j], переместите left_arr[i] to arr[k] и увеличьте i и k, в противном случае переместите right_arr[j] до arr[k] и увеличьте j и k.
Вот код для mergeSort:
Здесь, если элементов меньше 2, нам даже не нужно сортировать. Мы помещаем половину элементов в left_arr, другую половину в right_arr. Затем мы вызываем mergeSort и делим дальше на каждый подмассив — merge — это часть, которая фактически сортирует вещи вместе.
Вот код для слияния:
Как было сказано ранее, левый и правый индексы позволяют нам отслеживать текущий элемент для проверки как левого, так и правого подмассивов. Мы сравниваем эти значения и перемещаем меньшее значение в исходный массив. Из какого массива мы должны переместить меньший элемент, мы увеличиваем соответствующий индекс i или j на 1, а также k на 1.
Когда все будет готово, останется один из массивов с элементами для копирования. Если в левом подмассиве остались элементы, мы копируем оставшиеся элементы в исходный массив. В противном случае мы копируем остальные элементы из правого подмассива в исходный массив.
Для тех из вас, кто занят подготовкой к интервью, вы, вероятно, имеете в виду эти вопросы: в чем разница между быстрой сортировкой и сортировкой слиянием, пространством и сложностью?
Прежде всего, быстрая сортировка o(n²), когда речь идет о худшей производительности, o(n log n) о средней производительности. Всегда существует вероятность того, что каждый элемент нужно каждый раз поворачивать и разбивать. Он не требует дополнительной памяти, поэтому с точки зрения памяти это o (1).
Для получения дополнительной информации о быстрой сортировке вы можете прочитать мою статью здесь:
Сортировка слиянием, с другой стороны, всегда будет o(n log n), худшей или средней производительности. Однако при сортировке слиянием левый и правый подмассивы всегда должны быть выделены, поэтому с точки зрения памяти это o (n).
Вот как это происходит при сортировке слиянием. Теперь ваша очередь попрактиковаться в этих алгоритмах и понять, как они работают.
