[Powered by Google Translate] [Сортировка слиянием] [Rob Боуден - Гарвардский университет] [Это CS50. - CS50.TV] Давайте поговорим об сортировки слиянием. До сих пор вы видели пузырьковой сортировки, сортировки вставкой, и выбор рода. Хотя я вроде волне моей рукой на то, что я имею в виду лучше, сортировка слиянием обычно работает лучше, чем любой из этих 3 видов. 

Но прежде чем говорить о рода слияние, давайте поговорим о слиянии 2 отсортированных списков. Мы называем процесс занимает 2 отсортированных списков, как эти, и одним отсортированный список из них - слияние списков. Как мы можем это сделать? Ну, одна идея, это просто придерживаться одного списка в конец другого списка а затем отсортировать полученный список. 

Хотя это работает, это много ненужной работы. Мы можем сделать это быстрее, чем просто сортировка. Обратите внимание, что один неверный идея, чтобы просто взять переменный чашки из каждого списка. Хотя это может показаться, что работы на первой, Делая это, мы в конечном итоге с 4, 8, 15, 23, 16 - обратите внимание, что 16 и 23 являются неуместными. Это потому, что 2 элемента, которые должны появиться последовательно в объединенном списке находятся в том же первоначальный список. И 15 и 16 находятся в списке слева. Хитрость заключается в том, чтобы воспользоваться тем, что в обоих списках уже отсортированы. Это означает, что если мы просто посмотрим на первые элементы обоих списков - Здесь, 4 и 8 - один из них должен быть первым элементом объединенного списка. Ну, зачем это? Оба эти списки уже отсортированы, и так 4 или 8 должно быть наименьшим элементом, когда мы объединим 2 списка. В этом случае является наименьшим 4, так что мы можем взять из 4 и сделать его первым элементом нашего объединенного списка. Сейчас мы продолжаем слияния оставшиеся 3 элемента из первого списка и 4 элементы второго списка. 

Опять же, мы только должны смотреть на первый элемент обоих списках. Меньшее из 2 должны быть вторым элементом нашего объединенного списка. На этот раз, между 8 и 15 является наименьшим 8, и так мы вставляем, что в качестве второго элемента нашей отсортированный список. Мы можем продолжать сравнивать первые элементы обоих списков и удаления меньшее из 2. Сравнение 15 и 23, 15 и меньше, так вот наш третий элемент. Сравнивая теперь 16 и 23, 16 меньше. Так вот четвертый элемент. 

Обратите внимание, что 2 элемента пришли из того же списка в ряд. Именно поэтому объединенный список не может просто альтернативный элементов из 2 списка. Сравнение 50 и 23, 23 будет меньше, поэтому мы выбираем это. Между 50 и 42, 42 меньше. Между 50 и 108, 50 меньше. И, наконец, мы просто должны 108, поэтому она должна идти в конце нашего списка. Обратите внимание, что у нас есть хорошие, отсортированный список. Каждый раз, когда мы сравнивали первые 2 элемента из 2 списки Мы смогли определить следующий элемент объединенного списка. Это означает, что если окончательный список содержит номера п, где п здесь 8, Затем нам нужно не более п сравнений, чтобы получить все эти цифры в правильном месте. Такой алгоритм называется работать в линейном времени, но не беспокойтесь об этом здесь. 

Используя наш алгоритм слияния, мы можем сделать быстрый алгоритм сортировки слиянием. Итак, давайте сбросить наши списки. Есть 2 большие шаги в процессе сортировки слиянием. Во-первых, непрерывно разделить список чашки пополам до тех пор пока у нас есть куча списков только с 1 чашкой в ​​них. Не волнуйтесь, если список содержит нечетное число и вы не можете сделать идеально чистый срез между ними. Просто произвольно выбрать, какой список, включив дополнительную чашку дюйма Итак, давайте разделить эти списки. Теперь у нас есть 2 списка. Теперь у нас есть 4 списков. 

И теперь у нас есть 8 списков с одной чашки в каждом списке. Так вот оно что на шаге 1. Для шаге 2, мы неоднократно слияния пары списков с использованием алгоритма слияния мы узнали раньше. Слияние 108 и 15, мы в конечном итоге со списком 15, 108. Слияние 50 и 4, мы в конечном итоге с 4, 50. Слияние 8 и 42, мы в конечном итоге с 8, 42. И слияние 23 и 16, мы в конечном итоге с 16, 23. Теперь все наши списки размера 2. Обратите внимание, что каждый из 4 списки сортируются. 

Таким образом, мы можем начать слияние пары списки. Слияние 15 и 108, а 4 и 50 - сначала взять 4, то 15, то 50, то 108. Слияние 8, 42 и 16, 23, Возьмем сначала 8, затем 16, затем 23, затем 42. Так что теперь у нас есть всего 2 списки размер 4, каждая из которых сортируется. Итак, теперь мы объединить эти 2 списка. Сначала мы берем 4. Затем мы берем 8. Затем мы берем 15 и 16, то 23, то 42, то 50, то 108. И мы сделали. Теперь у нас есть отсортированный список. Так, как быстро было это на самом деле? С технической точки зрения, слияние сортировки O (п § п), в то время как все пузырьковой сортировки, сортировки вставкой, и выбор рода являются O (N ²). В самом деле, как вы узнаете в ближайшее время, вы не сможете придумать своего рода , что работает лучше, чем O (п § п) в общем случае. Опять же, не беспокойтесь об этом большом обозначение O, если вы его еще не видела. 

Просто знаю, что это значит, если мы хотим, чтобы отсортировать действительно большой список пузырьковая сортировка, сортировка вставкой, и выбор рода потенциально могут принимать значительно дольше, чем сортировка слиянием. Это не означает, что сортировка слиянием будет быстрее для всех списков или даже для любого единый список под определенный размер. Например, сортировка вставкой может быть самый быстрый вид для всех списков меньше, чем 5 элементов. На практике, сортировка слиянием, как правило, быстрее для списков как малые, как 50 элементов. 

Но эта дополнительная скорость не приходит без цены. В отличие от других сортов, которые принимают список и изменить список на месте пока мы не получим отсортированный список, сортировка слиянием необходимо дополнительное место объединить 2 списка вместе. Мы не можем сразу использовать списки, которые сливаются для хранения объединенного списка так как мы можем изменить элементы, которые еще должны быть объединены. Это пространство является немного цены, но это обычно не является необоснованным. И вот именно для сортировки слиянием. 

Меня зовут Боб Боуден, и это CS50. [CS50.TV] - И выбор рода. [Смеется] Ох, надо принять это слишком, потому что я перешел, как я представлял его. Список слева. Это была опечатка. [Оговорился] я облажался - [Смеется] Я не знаю, что -