Ах, алгоритмы сортировки. Обычно используется университетами, буткемпами и т.п., чтобы познакомить новичка с миром алгоритмов. К сожалению, это не всегда срабатывает, и новичку приходится изучать все больше и больше руководств, пока он, наконец, не сработает! Что ж, вот еще один, и я добавил мультфильмы, так что, надеюсь, это значительно облегчит обучение.

Небольшой совет перед тем, как начать. Несомненно, лучший способ выучить алгоритм — реализовать его по памяти. Просмотрите эти алгоритмы, но после этого попробуйте написать их с нуля в любом текстовом редакторе! Установите таймер на 25 минут и боритесь все 25 минут. Пишите подделки, пишите код, который не работает! Затем после того, как прозвенит таймер, сравните то, что у вас получилось, с справочными материалами. Определите пробелы в знаниях, прополощите и повторите, пока полностью не поймете. Сделайте это, и вы станете королем кодирования! Далее к алгоритмам...

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

Пожалуйста, извините мои крайне плохие способности к рисованию!

  1. Пузырьковая сортировка:

Несомненно, самый неэффективный из алгоритмов сортировки, временная сложность которого составляет O (n²), и он действительно полезен только при обучении алгоритмам. Чтобы понять алгоритм пузырьковой сортировки, я предоставил некоторый код в javascript:

Мы перебираем этот алгоритм n (длина массива) X n раз. Крайне неэффективно, но работает. Пузырьковая сортировка работает так, что она непрерывно перебирает массив заданной длины, а затем меняет местами в любом случае, когда два соседних элемента не отсортированы по значению. Это продолжается до тех пор, пока, наконец, не завершится один полный проход цикла без замены каких-либо элементов. Когда это происходит, переменная swap, которую мы объявляем, становится ложной и выходит из цикла while.

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

2. Сортировка вставками

Также алгоритм сортировки по временной сложности O (n²) в наихудшем случае, хотя и немного более интуитивно понятен, чем пузырьковая сортировка. Он не занимает много места, а для небольших списков выигрывает в скорости, поэтому об этом стоит помнить. Опять же, я предоставил некоторый код для сортировки вставками, давайте посмотрим на него, прежде чем углубляться в наш анализ + аналогия:

Вот алгоритм. Довольно простая реализация, нужно отметить лишь несколько важных моментов. В этом алгоритме сортировки мы начинаем со второй позиции (1-й индекс) массива. Почему? Поскольку мы хотим убедиться, что каждый элемент сортируется по мере продвижения вниз по массиву, мы можем просто поместить его в нужное место.

Итак, мы определяем временную переменную, чтобы она указывала на значение, которое мы сейчас имеем в массиве, затем мы хотим пройтись по длине и сравнить это значение с каждым значением перед ним. Поскольку массив уже отсортирован, когда мы двигаемся с нашим i-индексом, мы хотим сдвигать все, пока не найдем условие, при котором наша временная переменная больше, чем все остальное на оставшейся длине (отсюда j ≥ 0 И arr[j] › временное состояние). Именно туда мы вставляем нашу временную переменную, а затем просто перемещаемся вниз по массиву, пока не найдем каждый элемент.

Примечание. Некоторых новичков может запутать arr[j + 1], поэтому проверьте это. Когда мы перемещаемся вниз по длине массива с помощью j — , j-переменная деинкрементируется. Когда мы достигаем того конкретного значения, при котором наша временная переменная больше не является наименьшей из двух сравниваемых, цикл for останавливается. Однако переменная j сохраняется. Затем индекс j+1 относится к месту, в котором переменная temp больше не меньше значений, которые мы проверяли. Это тривиально для более продвинутых изучающих CS, но для новичка это может быть запутанным понятием, требующим глубоких знаний операций цикла for. Помните, что объявление var СБРОСАЕТ j-счетчик каждый раз, когда наш i-индекс увеличивается!

В нашем примере с тюрьмой охранник начал бы с заключенного на позиции № 2, сравните его с заключенным на позиции № 1, допустим, им приказано. Второй цикл for прерывается, и переменная j+1 представляет i-индекс, то же значение, поэтому тюремный охранник не производит обмен. Затем он переходит к следующему заключенному, этот парень намного ниже второго заключенного, но выше первого. Он заставляет этого заключенного выйти (назначая ему arr[i]), а затем сравнивает его с заключенным перед ним (arr[j]), этот парень выше, поэтому цикл for продолжает работать. Тюремный охранник велит заключенному №2 пересесть. Затем он спускается еще на одно место и смотрит на заключенного. Этот парень намного ниже ростом, чем заключенный №3. Цикл for прерывается, и индекс [j + 1] указывает на вторую позицию. Заключенный помещается туда. Он продолжает это для каждого заключенного, если будет большая очередь (тысячи заключенных) это тоже займет вечность!

3. Сортировка слиянием

Мой личный фаворит! Сортировка слиянием работает по принципу «разделяй и властвуй», разделяя массив заданной длины до тех пор, пока не будет получен массив длины 1, после чего вы начинаете процесс сортировки, затемслияния. Это рекурсивный алгоритм, поэтому его немного сложнее понять, но, надеюсь, я смогу изложить его в более простых терминах. Многие распространенные современные браузеры используют этот алгоритм сортировки, и его реализация довольно проста, давайте проверим это:

Давайте внимательно посмотрим на этот код. Он использует вспомогательную функцию, которая объединит два разделенных массива. В нашей функции mergeSort обратите внимание на базовый случай. Если длина массива равна единице, то мы возвращаем значение. В противном случае мы продолжаем разделять массив на две части. Каждая итерация определяет новый средний индекс. Затем этот средний индекс применяется для разделения левой и правой половин. Затем они передаются во вспомогательную функцию слияния, но только в том случае, если они возвращаются в виде массива, а не другой функции mergeSort.

Таким образом, этот алгоритм опускает нас на несколько уровней вниз, пока правая и левая части не будут иметь длину 1. Затем мы начинаем слияние. Вспомогательная функция слияния проста. У нас есть массив, в который мы продолжаем помещать данные. Мы хотим вставлять в этот массив до тех пор, пока существуют обе длины, потому что одна длина закончится быстрее, чем другая. Мы сравниваем элементы, помещаем меньший элемент в массив результатов и сокращаем длину массива, которому он изначально принадлежал.

В конце мы должны соединить остаток либо слева, либо справа. Поскольку это различается, мы вставляем код для обоих. После того, как эта функция завершается, мы перемещаемся вверх по цепочке, у нас есть массив, который мы затем запускаем слиянием снова и снова, пока не доберемся до самого верхнего уровня выполнения. Который затем должен вернуть отсортированный массив.

Временная сложность этого алгоритма делает его очень эффективным при O (n * log (n)).

В нашем примере с тюремным охранником тюремный охранник займет среднее положение, левая и правая стороны будут разделены. Затем он подходил к левой половине, делил их пополам. То же самое он проделал с правой стороной. Он делил половинки до тех пор, пока не оставался один заключенный, потом сравнивал этого заключенного слева от себя, сортировал их. Он сделал бы то же самое с другой стороны. Затем он сливал эти стороны. Потом сортировать, потом объединять, потом сортировать, потом объединять, пока не останется одна строка. С помощью этого процесса он мог сортировать 1000 заключенных намного быстрее, чем другие алгоритмы, которые мы видели до сих пор.

4. Быстрая сортировка

Это быстрее, чем даже сортировка слиянием! Хотя он должен быть эффективным в том, как он разбивает массив. Быстрая сортировка также является эффективным алгоритмом сортировки с той же средней временной сложностью, что и сортировка слиянием, но обычно работает немного лучше. Это также рекурсивная функция, использующая вспомогательный метод (в нашем случае два!). Быстрая сортировка также использует тот же принцип: мы выбираем опорную точку, затем делим массив в ней, а затем сортируем все в соответствии с этой опорной точкой. Затем мы выбираем новую точку разворота, затем делаем то же самое, пока все не будет отсортировано. Быстрая сортировка часто является самым сложным для понимания алгоритмом сортировки для новичков, поэтому не расстраивайтесь, если это не сработает:

Давайте начнем с изучения нашего алгоритма быстрой сортировки, давайте попробуем разобраться в этом построчно. Во-первых, на входе функции функция инициализирует входной параметр left и входной параметр right как 0, так и arr.length -1. Эти значения изменяются, когда мы рекурсивно вызываем эту функцию.

Затем у функции есть условный оператор, который проверяет длину записи. Это наш базовый случай. Если он не соответствует этому требованию, он даст нам эту длину в один массив.

Затем в следующей строке мы объявляем переменную idx, представляющую индекс, и вызываем вспомогательную функцию раздела.

Таким образом, мы воспользуемся преимуществами двух вспомогательных функций. Один очень простой, функция подкачки, чтобы поменять местами два заданных индекса. Однако функция разделения принимает массив, а также входные параметры левого и правого индекса. Давайте войдем внутрь.

Итак, мы получаем массив, и в первой итерации этой рекурсивной функции мы получаем 0 в качестве левого индекса и arr.length-1в качестве правого индекса. Мы получаем опорное значение, которое в данном случае мы определяем как среднеиндексированное значение из массива.

Затем запускается наш цикл while, и его условие завершается, если мы доходим до точки, в которой левый индекс больше правого индекса. Это необходимо для сохранения целостности нашей логики. Затем мы выполняем два других цикла while с аналогичными логическими потоками: эти два цикла while увеличивают левую сторону и уменьшают правую сторону, пока не дойдем до точки, где мы получим значение в левой части, которое больше, чем опорное значение, или мы получаем значение с правой стороны, которое меньше, чем значение разворота.

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

Затем эта функция секционирования возвращает левый индекс, который она пропускает. который затем присваивается переменной idx, затем он выходит за рамки и выполняется до тех пор, пока не будет отсортирован каждый элемент.

В тюремной охране, например, это было бы похоже на то, что тюремная охрана не делится посередине, а делится между случайным заключенным. Затем сравнивая рост других заключенных в соответствии с этим стержнем, более низкие слева и более крупные справа. Каждая из строк затем снова сортируется с помощью быстрой сортировки, выбора опорного заключенного и так далее, пока мы не получим правильный порядок.

Это сложно получить, продолжайте смотреть на это, продолжайте реализовывать его заново. Я обещаю вам, что он начнет щелкать!