Для классических алгоритмов вы тоже сталкивались с такой ситуацией: вы думаете, что это очень понятно, когда изучаете, но через некоторое время забываете?
Эта серия статей пытается решить эту проблему.
Изучая эти алгоритмы сортировки и внимательно изучая их имена, они на самом деле очень уместны.
Например, сортировка слиянием, «слияние», слово «рекурсивный» плюс «слияние». Это типичный алгоритм разделяй и властвуй.
На приведенном выше рисунке массив сначала делится на две части, затем каждая часть рекурсивно сортируется и, наконец, объединяется.
Среди них относительно легко делить и возвращать (будет описано позже) Суть алгоритма: как объединить два отсортированных массива?
Решение легко придумать, меньшее из двух.
Как показано на рисунке выше, каждое сравнение берет относительно небольшой элемент и помещает его в массив результатов.
Переведено в код:
let left = [2, 4, 6], i = 0
let right = [1, 3, 5], j = 0
let result = []
while(i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i])
i++
} else {
result.push(right[j])
j++
}
}
console.log(result) // [ 1, 2, 3, 4, 5 ]
В коде i и j являются нижними индексами двух массивов соответственно. После завершения обхода в массиве могут остаться какие-то остатки, и все они могут быть добавлены в результирующий массив:
if (i < left.length) {
result.push(...left.slice(i))
}
if (j < right.length){
result.push(...right.slice(j))
}
Примечание: чтобы было понятно, что любой из них можно оставить, if...else здесь прямо не используется. На самом деле никогда не будет случая, когда оба останутся (гарантировано циклом while). Кроме того, здесь используются API-интерфейсы, связанные с массивами (concat также может), или циклы могут использоваться напрямую.
И вот эта основная проблема решена, давайте посмотрим по пунктам и вернемся.
Что касается деления, просто разделите массив пополам от середины:
let m = Math.floor(array.length / 2)
let left = array.slice(0, m)
let right = array.slice(m)
Что же касается рекурсии, то она хоть и не соответствует линейному мышлению, но на самом деле несложна.
Пока есть рекурсивные шаги (рекурсивные формулы), их легко перевести в код.
Напомним шаги алгоритма слияния:
- Массив делится на две половины, левую и правую
- процесс левый рекурсивно
- Право на рекурсивную обработку
- Объединить два результата
Легко переводится в код:
function mergeSort(array) {
let m = Math.floor(array.length / 2)
let left = mergeSort(array.slice(0, m))
let right = mergeSort(array.slice(m))
return merge(left, right)
}
Рекурсия вызывает сама себя, и ее нельзя вызывать бесконечно, поэтому требуется рекурсивный выход (начальное условие).
Его рекурсивный выход заключается в том, что когда количество элементов в массиве меньше 2, он уже отсортирован, и нет необходимости в рекурсивных вызовах.
Итак, вам нужно добавить код впереди:
if (array.length < 2) {
return array
}
См. полный код:codepen.
На данный момент принцип и реализация сортировки слиянием завершены.
Подводя итог, можно сказать, что для сортировки слиянием требуется дополнительное пространство, а пространственная сложность составляет O(n). Временная сложность составляет O(nlogn), что является отличным алгоритмом и имеет высокую вероятность появления в вопросах на собеседовании.
Сортировка слиянием и быстрая сортировка, о которых пойдет речь в следующей статье, — это алгоритмы «разделяй и властвуй», которые требуют деления, слияния и слияния. Первый фокусируется на том, как слиться, а второй — на том, как разделить.
Сортировка слиянием, чтобы иметь возможность написать ее от руки за считанные минуты, необходимо освоить принцип ее сортировки. Суть в том, чтобы объединить два рекурсивно отсортированных массива, выбрав меньшее из сравниваемых. Что касается рекурсии, то до тех пор, пока рекурсивные шаги и выходы могут быть четко указаны, ее можно легко записать без механического запоминания.
Надеюсь, что это поможет, эта статья закончилась.
Статьи, опубликованные в этой серии: