Введение в алгоритмы сортировки в JavaScript
Подобно большинству других языков программирования, вы можете столкнуться со сценариями, в которых вам нужно отсортировать некоторые числа в JavaScript в порядке возрастания или убывания. Чтобы сделать это, мы можем использовать множество алгоритмов, таких как Bubble sort, Selection Sort, Merge sort, Quicksort и т. Д. Эти алгоритмы не только отличаются друг от друга тем, как они работают, но также у каждого свои требования с точки зрения памяти и времени, давайте углубиться в некоторые из важных алгоритмов сортировки и посмотреть, как вы можете использовать их в своем коде JavaScript.
6 лучших алгоритмов сортировки в JavaScript
Вот некоторые алгоритмы сортировки в JavaScript, объясненные ниже примерами:
1. Алгоритм пузырьковой сортировки
Считающийся одним из наиболее распространенных инструментов в этой торговле, сортировка Bubble работает путем создания цикла, который сравнивает каждый элемент в массиве с другим элементом. Если сравниваемый элемент меньше, чем тот, который имеется в наличии, мы меняем их местами. Это продолжается до тех пор, пока у нас не будет прохода, при котором ни один элемент в массиве не будет больше элемента, который находится рядом с ним.
Bubble Sort имеет O (n 2 ) временную сложность и O (n) пространственную сложность.
Код:
function swap(arr, firstIndex, secondIndex)(
var temp = arr(firstIndex);
arr(firstIndex) = arr(secondIndex);
arr(secondIndex) = temp;
)
function bubbleSortAlgo(arraaytest)(
var len = arraaytest.length,
i, j, stop;
for (i=0; i < len; i++)(
for (j=0, stop=len-i; j < stop; j++)(
if (arraaytest(j) > arraaytest(j+1))(
swap(arraaytest, j, j+1);
)
)
)return arraaytest;
)
console.log(bubbleSortAlgo((3, 6, 2, 5, -75, 4, 1)));
Выход:
2. Алгоритм выбора сортировки
Теперь, когда мы закончили обсуждение алгоритма Bubble Sort, давайте рассмотрим просто популярный алгоритм сортировки Selection Sort.
В отличие от Bubble Sort, мы сосредоточены на поиске наименьшего значения в массиве, чтобы выполнить сортировку. Вот пошаговая разбивка того, как работает Selection Sort:
- Мы принимаем первый элемент в массиве как самый маленький.
- Мы сравниваем этот элемент со следующим элементом в массиве.
- Если следующий элемент меньше текущего, мы устанавливаем следующий элемент как новое наименьшее значение.
- Мы продолжаем повторять эти шаги, пока не достигнем конца массива.
- Когда мы находим значение в массиве меньше, чем тот, с которого мы начали, мы меняем их позиции.
- Мы продолжаем сравнивать и переходить к следующему пункту. Пока весь массив не отсортирован.
Как и алгоритм Bubble Sort, сортировка Selection имеет O (n 2 ) временную сложность и O (n) пространственную сложность.
Код:
function SelectionSortAlgo(array, compare_Function) (
function comp(a, b) (
return a - b;
)
var min = 0;
var index = 0;
var temp = 0;
compare_Function = compare_Function || compare;
for (var i = 0; i < array.length; i += 1) (
index = i;
min = array(i);
for (var j = i + 1; j < array.length; j += 1) (
if (compare_Function(min, array(j)) > 0) (
min = array(j);
index = j;
)
)
temp = array(i);
array(i) = min;
array(index) = temp;
)
return array;
)
console.log(SelectionSortAlgo((9, 15, 2, 44, -1, 36, 1), function(a, b) ( return a - b; )));
Выход:
3. Алгоритм сортировки слиянием
Подобно Bubble Sort и Selection Sort, сортировка по слиянию является одним из популярных алгоритмов сортировки в компьютерных науках, вы можете реализовать его на большинстве языков программирования, и она имеет хорошую производительность, не требуя слишком много ресурсов.
Merge Sort использует метод Divide and conquer для сортировки массива или любого списка элементов. Термин «разделяет и побеждает» означает, что мы делим одну большую проблему на несколько более мелких, а затем решаем эти небольшие проблемы. Как только меньшие проблемы решены, мы объединяем результаты, которые приводят к решению большой проблемы.
На самом деле понять алгоритм просто:
- Разобьем данный массив на n массивов, каждый из которых содержит всего 1 элемент.
- Объедините массивы, чтобы создать новый массив.
- Повторяйте шаг 2, пока не останется только 1 массив, который будет отсортированным массивом.
Код:
function merge_sort_algo(left, right)
(
var i = 0;
var j = 0;
var result = ();
while (i < left.length || j < right.length) (
if (i === left.length) (
// j is the only index left_part
result.push(right(j));
j++;
)
else if (j === right.length || left(i) <= right(j)) (
result.push(left(i));
i++;
) else (
result.push(right(j));
j++;
)
)
return result;
)
console.log(merge_sort_algo((1, 44, 6), (84, 7, 5)));
Выход:
4. Алгоритм быстрой сортировки
Quicksort является одним из наиболее эффективных способов сортировки элементов в компьютерных системах. Подобно сортировке слиянием, Quicksort работает над алгоритмом «разделяй и властвуй». В этом мы находим элемент сводки в массиве для сравнения всех других массивов элементов, а затем перемещаем элементы таким образом, чтобы все элементы до выбранных нами элементов сводились меньше, а все элементы после элемента сводки были больше по размеру. Как только мы это сделаем, ключ в том, чтобы продолжать делать это многократно, и у нас будет наш отсортированный массив.
Ниже приведены шаги, которые можно выполнить для реализации алгоритма быстрой сортировки:
- Мы выбираем элемент массива и называем его «Точка разворота»
- Мы запускаем указатель, называемый левым указателем, который находится у первого элемента в массиве.
- Точно так же мы запускаем указатель, называемый правым указателем на последний элемент в массиве.
- Если значение элемента у левого указателя меньше по сравнению с выбранной точкой поворота, мы перемещаем левый указатель влево (добавляем +1 к нему) и повторяем его до тех пор, пока значение у левого указателя не будет больше значения значение точки разворота или равно ей.
- Если значение элемента по правому указателю в списке выше, чем значение элемента pivot, мы переключаем правый указатель влево. Повторяйте это до тех пор, пока значение на указателе справа не станет меньше (или равно) значению pivot.
- Если значение левого указателя меньше или равно значению правого указателя, меняйте местами значения.
- Переместите правый указатель влево на один, левый указатель вправо на один.
- Повторяйте, пока не встретятся левый и правый указатели.
Код:
function quickSortAlgo(origArray) (
if (origArray.length <= 1) (
return origArray;
) else (
var left = ();
var right = ();
var newArray = ();
var pivot = origArray.pop();
var length = origArray.length;
for (var i = 0; i < length; i++) (
if (origArray(i) <= pivot) (
left.push(origArray(i));
) else (
right.push(origArray(i));
)
)
return newArray.concat(quickSortAlgo(left), pivot, quickSortAlgo(right));
)
)
var myArray = (13, 50, 2, 45, -1, 74, 11 );
var arreySorted = quickSortAlgo(myArray);
console.log(arreySorted);
Выход:
5. Алгоритм сортировки вставок
Когда дело доходит до простоты реализации, сортировка вставок широко известна как один из более простых алгоритмов. При сортировке вставкой элементы массива сравниваются друг с другом, а затем располагаются в определенном порядке. Это очень похоже на размещение карт в колоде. Сортировка вставки имени происходит из процесса выбора элемента и вставки его в правильное место, а затем повторения его для всех элементов.
Вот как работает алгоритм:
- Первый элемент массива считается уже отсортированным.
- Выберите следующий элемент массива.
- Сравните выбранный элемент со всеми элементами в массиве.
- Сдвиньте каждый элемент в массиве, который больше, чем значение выбранного элемента.
- Вставить элемент
- Повторите шаги с 2 по 5, пока массив не будет отсортирован.
Код:
function insertion_Sort_algo(arr)
(
for (var i = 1; i < arr.length; i++)
(
if (arr(i) < arr(0))
(
arr.unshift(arr.splice(i, 1)(0));
)
else if (arr(i) > arr(i-1))
(
continue;
)
else (
for (var j = 1; j < i; j++) (
if (arr(i) > arr(j-1) && arr(i) < arr(j))
(
arr.splice(j, 0, arr.splice(i, 1)(0));
)
)
)
)
return arr;
)
console.log(insertion_Sort_algo((44, 20, 26, 54, -9, 41, 16)));
Выход:
6. Алгоритм сортировки кучи
Сортировка кучи - это способ сортировки элементов с использованием структуры данных «Куча». Этот метод очень похож на метод сортировки выбора, который мы обсуждали ранее. Теперь вы можете задаться вопросом о кучах и о том, как они определены, прежде чем перейти к алгоритму, давайте разберемся с кучами.
В двух словах, куча - это двоичное дерево с некоторыми добавленными правилами. Одно правило гласит, что в куче дерево должно быть полным двоичным деревом, что просто означает, что необходимо заполнить все узлы на текущем уровне, прежде чем добавлять другой. Следующее правило для кучи состоит в том, что должны быть определенные дочерние и родительские отношения со значениями элементов кучи.
В минимальной куче значение родителя должно быть меньше его потомков. В максимальной куче, как вы можете догадаться, значение родительского элемента должно быть больше, чем его дочерний элемент.
Теперь, когда определения вышли из моды, давайте посмотрим, как работает heapsort:
- Сначала мы строим максимальную кучу, которая гарантирует, что элемент с самым высоким значением находится сверху.
- Мы переключаем верхний элемент с последним элементом кучи, удаляем верхний элемент из кучи и сохраняем его в отсортированном массиве.
- Мы продолжаем повторять шаги один и два, пока в куче не останется только один элемент.
Следует иметь в виду, что кучи не поддерживаются в JavaScript изначально, поэтому мы должны прибегнуть к реализации кучи с использованием массивов. Пространственная сложность сортировки кучи - O (1), которая превосходна, и хотя она немного сложнее по сравнению с сортировкой слиянием или сортировкой вставкой, когда речь идет о понимании и реализации, я думаю, что для повышения производительности ее в конечном итоге лучше использовать в крупные проекты.
Код:
var arrLength;
function heapRoot(input, i) (
var left = 2 * i + 1;
var right = 2 * i + 2;
var max = i;
if (left input(max)) (
max = left;
)
if (right input(max)) (
max = right;
)
if (max != i) (
swap(input, i, max);
heapRoot(input, max);
)
)
function swap(input, index_A, index_B) (
var temp = input(index_A);
input(index_A) = input(index_B);
input(index_B) = temp;
)
function heapSortAlgo(input) (
arrLength = input.length;
for (var i = Math.floor(arrLength / 2); i >= 0; i -= 1) (
heapRoot(input, i);
)
for (i = input.length - 1; i > 0; i--) (
swap(input, 0, i);
arrLength--;
heapRoot(input, 0);
)
)
var arr = (12, 10, 22, 55, -8, 64, 14);
heapSortAlgo(arr);
console.log(arr);
Выход:
Вывод
Сортировка является важной частью создания приложений и веб-сайтов с помощью JavaScript. Теперь, когда вы знакомы с некоторыми из наиболее важных алгоритмов для выполнения работы, вы должны чувствовать себя более уверенно в JS Development.
Один важный факт, о котором следует помнить о различной сортировке, заключается в том, что вам не нужно слишком сильно напрягаться в отношении того, какой алгоритм использовать в большинстве случаев. Теперь, когда аппаратное обеспечение компьютера настолько мощное, современные процессоры для телефонов и настольных ПК не будут потеть, сортируя даже сотни элементов за несколько миллисекунд. Только в тех случаях, когда вы застряли на медленном оборудовании, или в ситуациях, когда вы оптимизируете каждый отдельный фрагмент кода, изменение алгоритмов сортировки может быть полезным.
Рекомендуемые статьи
Это руководство по алгоритмам сортировки в JavaScript. Здесь мы обсуждаем 6 лучших алгоритмов сортировки в javascript вместе с примерами и реализацией кода. Вы также можете посмотреть следующие статьи, чтобы узнать больше -
- Компиляторы JavaScript
- Обратный в JavaScript
- Введение в JavaScript
- Квадраты в Яве
- Алгоритмы быстрой сортировки в Java
- Массивы в структуре данных
- С ++ Алгоритм | Примеры алгоритма C ++