Сортировка слиянием (простой способ понимания сортировки слиянием)

Нам предоставляется массив с элементами, и мы разбиваем этот массив, пока каждый элемент не будет разделен друг с другом и отсортирован. После этого они объединяются, чтобы вернуть объединенный массив отсортированных элементов. Именно это и будет делать сортировка слиянием.
Так просто! Давайте приступим без лишних слов.

Мы начинаем сравнивать элементы друг с другом, если элемент меньше другого, он переходит в объединенный массив и увеличивает индекс массива этого меньшего элемента.

Диаграммы ниже хорошо объясняют алгоритм, используемый для быстрой сортировки с объединением.

function merge(array1, array2) {
    let combined = []
    let i = 0
    let j = 0
    while(i < array1.length && j < array2.length) {
        if(array1[i] < array2[j]) {
            combined.push(array1[i])
            i++
        } else {
            combined.push(array2[j])
            j++
        }
    }
    while(i < array1.length) {
        combined.push(array1[i])
        i++
    }
    while(j < array2.length) {
        combined.push(array2[j])
        j++
    }
    return combined
}

function mergeSort(array) {
    if(array.length === 1) return array

    let mid = Math.floor(array.length/2)
    let left = array.slice(0,mid)
    let right = array.slice(mid)

    return merge(mergeSort(left), mergeSort(right))
}
Вход в полноэкранный режим Выход из полноэкранного режима

Протестируйте сортировку слиянием, вызвав эту функцию: mergeSort([1,3,7,8,2,4,5,6])

Оцените статью
devanswers.ru
Добавить комментарий