[Powered by Google Translate] TOMMY: Давайте взглянем на выбор рода, алгоритм
для принятия списка чисел и сортировка их.
Алгоритм, помните, это просто шаг за шагом
Процедура для выполнения задачи.
Основная идея выбора рода заключается в разделении
наш список на две части -
отсортировано части и несортированные часть.
На каждом шаге алгоритма, числа перемещается из
несортированные части к отсортированы часть пока в конце концов
Весь список отсортирован.
Итак, вот список из шести цифр -
23, 42, 4, 16, 8 и 15.
Сейчас весь список считается отсортированы.
Хотя число как 16 уже может быть в правильном
место, наш алгоритм не имеет возможности узнать, что до
Весь список отсортирован.
Таким образом, мы будем рассматривать каждый номер, который будет несортированные, пока мы не сортировать
это сами.
Мы знаем, что мы хотим, чтобы список, который будет в порядке возрастания.
Поэтому мы хотим создать отсортированный часть нашего списка
слева направо, от меньшего к большему.
Чтобы сделать это, нам нужно найти минимальный элемент несортированные
и положил его в конце отсортированы часть.
Поскольку этот список не отсортирован, единственный способ сделать это, чтобы
смотреть на каждый элемент в несортированный часть, вспомнив
какой элемент является самым низким и сравнивая
каждый элемент этого.
Таким образом, мы сначала смотрим на 23.
Это первый элемент, который мы видели, поэтому мы будем помнить
это как минимум.
Далее мы рассмотрим 42.
42 больше чем 23, поэтому 23 по-прежнему является минимальным.
Далее идет 4, который является меньше, чем 23, так что мы помним 4
как новый минимум.
Далее идет 16, которая больше 4, поэтому 4
по-прежнему является минимальным.
8, размер которых превышает 4, а 15 больше 4, поэтому 4 должна быть
наименьший элемент несортированные.
Так что, хотя, как и люди, мы можем сразу увидеть, что 4
минимального элемента, наш алгоритм должен смотреть на
каждый элемент несортированные, даже после того, как мы нашли 4 -
минимальный элемент.
Так что теперь мы нашли минимальный элемент, 4, мы хотим
чтобы переместить его в отсортированном часть списка.
Так как это первый шаг, это означает, что мы хотим поставить 4 на
В начале списка.
Сейчас 23 находится в начале списка, так
Давайте обмениваться 4 и 23.
Так что теперь наш список выглядит следующим образом.
Мы знаем, что 4 должен находиться в своем окончательном месте, потому что это
как наименьший элемент и элемент в начале
списка.
Таким образом, это означает, что мы никогда не должны переместить его снова.
Так давайте повторим этот процесс, чтобы добавить еще один элемент
отсортировано часть списка.
Мы знаем, что мы не должны смотреть на 4, потому что это
уже отсортированы.
Таким образом, мы можем начать в 42, в которой мы будем помнить, как
минимальный элемент.
Так что в следующий мы будем смотреть на 23, что меньше, чем 42, поэтому мы
помню 23 является новым минимумом.
Далее мы видим 16, который меньше, чем 23, поэтому
16 является новым минимумом.
Теперь мы смотрим на 8, который меньше, чем 16, так
8 является новым минимумом.
И, наконец, 8 меньше, чем 15, так что мы знаем, что 8 является минимальным
несортированные элемент.
Значит, мы должны добавить 8 до отсортированный
часть списка.
Сейчас 4 является единственным отсортированный элемент, поэтому мы хотим поместить
8 вперед на 4.
С 42 является первым элементом в несортированный часть
Список, мы хотим, чтобы обменять 42 и 8.
Так что теперь наш список выглядит следующим образом.
4 и 8 представляют собой упорядоченные части списка, а
Остальные цифры представляют несортированные
часть списка.
Так что давайте продолжать с другой итерации.
Мы начинаем с 23 на этот раз, так как мы не должны смотреть на
4 и на 8 больше, потому что они
уже отсортированы.
16 меньше 23, поэтому мы будем помнить
16 в качестве нового минимума.
16 меньше 42, а 15 меньше 16, так 15 должно быть
минимальный несортированные элемент.
Итак, теперь мы хотим, чтобы поменять 15 и 23 по
дайте нам этот список.
Отсортировано часть списка состоит из 4, 8 и 15, и
эти элементы по-прежнему отсортированы.
Но так уж случилось, что следующий элемент несортированные, 16,
уже отсортированы.
Однако, нет никакого способа для нашего алгоритма, чтобы узнать, что 16
уже в правильном месте, поэтому мы все еще должны
Повторяю точно такой же процесс.
Итак, мы видим, что 16 меньше, чем 42, и 16 меньше 23, поэтому
16 должен быть минимальным элементом.
Невозможно обменять этот элемент сам с собой, поэтому мы можем
Просто оставьте его в этом месте.
Так что нам нужно еще один проход нашего алгоритма.
42 больше 23, поэтому 23 должно быть
минимальная несортированные элемент.
После того как мы переставляем 23 и 42, мы в конечном итоге с нашей последней
отсортированный список -
4, 8, 15, 16, 23, 42.
Мы знаем, что 42 должны быть в правильном месте, так как это
Единственный элемент оставили, и это выбор рода.
Давайте теперь оформить наш алгоритм с некоторыми
псевдокод.
На первой линии, мы видим, что нам нужно интегрировать по
каждый элемент списка.
За исключением последнего элемента, так как 1 элемент
список уже отсортирован.
На второй линии, мы рассмотрим первый элемент несортированные
Часть списка, чтобы быть минимальным, как мы сделали с нашим
Например, у нас есть что-то для сравнения.
Третья строка начинается второй цикл, в котором мы перебора
каждый несортированные элемент.
Мы знаем, что после того как я итераций, отсортированные части
из нашего списка должны иметь элементы я в нем с каждым шагом
виды одного элемента.
Таким образом, первый несортированные элемент должен находиться в положении я плюс 1.
На четвертой строке, мы сравниваем текущий элемент к минимуму
элемент, который мы видели до сих пор.
Если текущий элемент меньше, чем минимальная
элемент, то мы помним, текущий элемент в качестве новой
Минимум на линии пять.
Наконец, на линии шесть и семь, мы переставляем минимальной
элемент с первым элементом несортированные, таким образом,
добавить его в отсортированном часть списка.
Как только мы получим алгоритм, важный вопрос
себя в качестве программистов как долго это займет?
Мы сначала задать вопрос, сколько времени потребуется для этого
Алгоритм для работы в худшем случае?
Напомним, мы представляем этот ход
Время с большой обозначение O.
Для того, чтобы определить минимальное несортированные элемент,
по существу было сравнить каждый элемент в списке
любой другой элемент в списке.
Интуитивно, это звучит как O п квадрат операции.
Глядя на нашем псевдокоде, мы также имеем цикл вложен в
другой цикл, который действительно звучит как O
п квадрат операции.
Однако помните, что мы не должны смотреть на
Весь список при определении минимального несортированные элемент?
Как только мы знали, что 4 был отсортирован, например, мы не
нужно смотреть на это снова.
Значит ли это, нижняя время работы?
Для нашего списка длина 6, нам нужно было сделать пять
сравнений для первого элемента, четыре сравнений для
Второй элемент, и так далее.
Это означает, что общее количество шагов является суммой
числами от 1 до длины списка минус 1.
Мы можем представить это с помощью суммирования.
Мы не будем вдаваться в суммах здесь.
Но оказывается, что это суммирование равна п раз
N минус 1 по 2.
Или, что эквивалентно, п квадрат более 2 минуса п над 2.
Когда речь идет об асимптотической выполнения, это п квадрат срок
будет доминировать в этой п срок.
Таким образом, выбор сортировки O п квадрат.
Напомним, что в нашем примере, выбор рода все еще нуждаются в
проверьте номер, который был уже отсортирован
Необходимо перемещать.
Таким образом, это означает, что если мы побежали выбор рода на уже
отсортированный список, это потребует столько же шагов, как это
бы при работе над вполне несортированный список.
Таким образом, выбор рода имеет лучшем случае выполнения п квадратов,
которые мы представляем с омега N в квадрате.
И вот именно для выбора рода.
Это лишь один из многих алгоритмов можно
использовать для сортировки списка.
Меня зовут Томми, и это CS50.