Человек может то, что он должен (И. Фихте).

Как работает алгоритм сортировки слияния

2 мин для чтения
FavoriteLoadingДобавить в избранное
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (1 оценок, среднее: 5,00 из 5)
Загрузка...
9 ноября 2018
Как работает алгоритм сортировки слияния
Алгоритм сортировки слиянием был изобретен Джоном фон Нейманом в 1945 году. Это эффективный алгоритм, используется подход разделяй и властвуй.

  1. Сортировка слиянием несколько раз делит массив на более мелкие куски, до тех пор, пока мы больше не сможем разделить массив на куски.
  2. Он повторно объединяет фрагменты массива для получения отсортированного массива.

Пример: [3,4,2,1]

1. Во-первых, мы должны разделить массив на более мелкие куски.

left  [ 3 , 4 ]     right [ 2, 1 ]
[ 3 ] [ 4 ]      [ 2 ] [ 1]

 

2. Мы должны объединить меньшие куски, чтобы получить сортированный массив. Сравниваем 3 и 4 они уже отсортированы, в следующем 2 и 1 поставить 1первый на место второго.

left   [ 3 , 4 ]     right [ 2, 1 ]
[ 3 ]  [ 4 ]      [ 2 ] [ 1]
[3, 4 ]          [1 ,2 ]

Теперь сравните индекс левой части 0 и индекс правой части 0, которые являются 3 и 1.

где 1 меньше 3, поэтому мы удаляем 1 из правой части и помещаем в сортированный список.

left  [ 3 , 4 ]     right [ 1, 2 ]
[ 3]  [ 4 ]      [ 2 ] [ 1]
[3, 4 ]          [ 2 ]
sorted array  [ 1 ]

 

Снова проверяем 3 и 2 и удаляем 2 из правой части и добавляем в сортированный список

left  [ 3 , 4 ]     right [ 1, 2 ]
[ 3]  [ 4 ]      [ 2 ] [ 1]
[3, 4 ]           [  ]
sorted array  [ 1 ,2 ]

 

Теперь добавьте левую и правую части с отсортированным списком.

left  [ 3 , 4 ]     right [ 1, 2 ]
[ 3]  [ 4 ]      [ 2 ] [ 1]
[3, 4 ]           [  ]
sorted array  [ 1 ,2 ,3, 4]

 

Давайте реализуем алгоритм сортировки слиянием

function mergeSort(array,half = array.length/2){
if(array.length < 2){
    return array  // это значит, что мы больше не делим массив
                  // на более мелкие куски
  }
const left = array.splice( 0,half ); //левая часть массива
return merger( mergeSort( left ),mergeSort( array ) )
}

 

В приведенном выше коде мы используем метод splice, который удаляет левую часть массива, так что оставшаяся часть массива является правой.

Далее нам нужно написать функцию слияния, которая поможет нам объединить левую и правую часть массива и вернет отсортированный список.

function merger(left, right) {
    const arr = [  ];
    while (left.length && right.length) {
        if (left[ 0 ] < right[ 0 ]) { 
            arr.push( left.shift( ) ) 
        } else {
            arr.push( right.shift(  ) ) 
        }
    }
    return [ ...arr, ...left, ...right ]; 
}

 

Итого

conlole.log(mergeSort([10, 5, 3, 8, 2, 6, 4, 1, 7, 9]));
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]]

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.

Просмотров: 9

Если статья понравилась, то поделитесь ей в социальных сетях:

Добавить комментарий

Войти с помощью: 

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Сообщить об опечатке

Текст, который будет отправлен нашим редакторам:

Заполните форму и наш менеджер перезвонит Вам в самое ближайшее время!

badge
Обратный звонок 1
Отправить
galka

Спасибо! Ваша заявка принята

close
galka

Спасибо! Ваша заявка принята

close