Хорошо, я прохожу вторую часть алгоритмов сортировки. Если вы пропустили часть 1, прочтите мой блог здесь! В прошлом блоге я рассмотрел алгоритмы сортировки выделения, пузырьков и вставки. Все они требовали вложенных циклов, что давало им временную сложность O (n²). Для этого мы рассмотрим те, которые немного лучше по временной сложности, такие как O (n log n), которые лучше подходят для больших наборов данных.

На приведенном выше графике вы можете видеть, что есть некоторое преимущество с временной сложностью n log n, следовательно, более быстрое выполнение, что всегда важно для компьютера и взаимодействия с пользователем.

Сортировка кучи

Этот алгоритм сортировки использует двоичную кучу для сортировки массива. Но что такое двоичная куча?

Двоичные кучи

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

В двоичных кучах элементы в дереве хранятся в особом порядке, где родительский узел либо больше (максимальная куча), либо меньше (минимальная куча), чем значения двух его дочерних узлов. С помощью Heap Sort создается максимальная куча!

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

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

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

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

Выбор того, какой элемент является опорным, определит, как будет происходить этот тип сортировки. Сводная точка может быть первым, последним, средним или случайным элементом массива. В моем примере я выберу средний элемент в качестве стержня. Просмотрите код ниже:

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

Подобно быстрой сортировке выше, этот алгоритм сортировки работает, разделяя массив пополам и вызывая себя на половинки. После того, как массив разделен на несколько массивов с одним элементом в них, функция слияния соберет их все вместе в отсортированный массив. Обычно временная сложность составляет O (n log n), но существуют другие обстоятельства для других временных сложностей. Просмотрите код ниже:

Сортировка слиянием - это мой алгоритм сортировки, поскольку он имеет временную сложность O (n log n), его легко понять и научить. Как уже говорилось ранее, существует гораздо больше алгоритмов сортировки. Найдите то, что лучше всего работает для вас!

Ресурсы:

  1. Объяснение алгоритмов сортировки, FreeCodeCamp, по состоянию на 15 октября 2020 г., https://www.freecodecamp.org/news/sorting-algorithms-explained/
  2. JS: Sorting Algorithms, по состоянию на 15 октября 2020 г., https://khan4019.github.io/front-end-Interview-Questions/sort.html
  3. Временные сложности всех алгоритмов сортировки, GeeksForGeeks, по состоянию на 15 октября 2020 г., https://www.geeksforgeeks.org/time-complexities-of-all-sorting-algorithms/
  4. Heap Sort, GeekForGeeks, по состоянию на 17 октября 2020 г., https://www.geeksforgeeks.org/heap-sort/
  5. Heapsort for Javascript Newbies, GitConnected, по состоянию на 17 октября 2020 г., https://levelup.gitconnected.com/heapsort-for-javascript-newbies-598d25477d55
  6. Quick Sort, GeekForGeeks, по состоянию на 16 октября 2020 г., https://www.geeksforgeeks.org/quick-sort/
  7. Сортировка слиянием, GeekForGeeks, по состоянию на 16 октября 2020 г., https://www.geeksforgeeks.org/merge-sort/