Основы программирования. Сортировка методом слияния

Рет қаралды 47,410

7 жыл бұрын

Весь курс CS50 - javarush.com/s/course_cs50
В видео разберемся, с понятием сортировки слиянием, и поймем, как можно её реализовать с помощью рекурсии. Снова разделяем и властвуем, уже практически по привычке.
Фрагмент из 8 лекции курса CS50

Пікірлер: 24

@krukah1 7 жыл бұрын

На мой взгляд он ни разу не упомянул принцип мерджа списков, что самое важное в данном случае.

@valeriyvaleriy9563 7 жыл бұрын

Поддерживаю. Ждал когда он объяснит про само слияние, вместо этого он раз по сто повторил левая часть, правая часть и ещё сто раз тронул себя за лоб.. >:/

@6161k 6 жыл бұрын

@jetli1311 6 жыл бұрын

kzbin.info/www/bejne/bKjSc6qiopaniK8

@TheProfessionalGambler 3 жыл бұрын

он начал объяснять мерж на 9:50

@Ivan-nm9yo 3 жыл бұрын

Бесполезное обьяснение, никак не обьясняется само слияние, как там реализована вставка в правильном порядке

@ruslansitdikov1489 3 жыл бұрын

God bless you!! This explanation saved my brain!!!

@MegaDecole 7 жыл бұрын

Спасибо за перевод!!! Очень полезная инфа

@736939 6 жыл бұрын

Алгоритмы от молодого Брюса Уиллиса

@BeloFFSergey 7 жыл бұрын

что делать если исходный список не кратен двум?

@forsic1 7 жыл бұрын

Сергей Белов добавить нулевой элемент )

@kpecmuk 7 жыл бұрын

по коду не важно кратно оно двум или нет. ты же итератор перемещаешь пока он < .length()

@ruslansitdikov1489 3 жыл бұрын

ничего не делать. разбивка идёт до каждого элемента и потом также сливается

@bogdantymKOLUBO 4 жыл бұрын

в самом конце он и рассматривает как происходит слияние на самых длинных кусках массива

@user-lj8by1ln8v 7 ай бұрын

Для простоты понимания - сплит с мерджем: class MyClass { public static void main(String[] args) { System.out.println(Arrays.toString(split(new int[] {5,4,3,2,1}))); } public static int[] split(int[] array) { if (array.length == 1) return array; if (array.length == 2) return mergeArrays(new int[] {array[0]}, new int[] {array[1]}); int[] left = new int[array.length / 2]; int[] right = new int[array.length - array.length / 2]; System.arraycopy(array, 0, left, 0, left.length); System.arraycopy(array, left.length, right, 0, right.length); return mergeArrays(split(left), split(right)); } public static int[] mergeArrays(int[] a1, int[] a2) { int[] a = new int[a1.length + a2.length]; int i = 0, i1 = 0, i2 = 0; while (i1 < a1.length && i2 < a2.length) a[i++] = a1[i1] < a2[i2] ? a1[i1++] : a2[i2++]; while (i1 < a1.length) a[i++] = a1[i1++]; while (i2 < a2.length) a[i++] = a2[i2++]; return a; } }