Сортиране на алгоритми в JavaScript - Топ 6 алгоритъм за сортиране в JavaScript

• Въведение в сортирането на алгоритми в JavaScript

Въведение в сортирането на алгоритми в JavaScript

Подобно на повечето други езици за програмиране, можете да се сблъскате със сценарии, където трябва да сортирате някои числа в JavaScript по възходящ или низходящ ред. За да го направим, можем да използваме много алгоритми като сортиране на балончета, сортиране на селекция, сортиране на сливане, Quicksort и др. Тези алгоритми се различават не само по начина на работа, но и всеки има своите различни изисквания по отношение на паметта и времето, отнесено копайте по-дълбоко в някои от важните алгоритми за сортиране и вижте как можете да ги използвате във вашия JavaScript код.

Топ 6 алгоритми за сортиране в JavaScript

Ето някои алгоритми за сортиране в JavaScript, обяснени по-долу с примери:

1. Алгоритъм за сортиране на балончета

Смятан за един от най-разпространените инструменти на тази търговия, сортирането на Bubble работи, като създава цикъл, който сравнява всеки елемент от масива с друг. Ако сравненият артикул е по-малък от този на ръка, ние разменяме местата им. Това продължава, докато нямаме пас, в който нито един елемент от масива не е по-голям от този, който е до него.

Bubble Sort има O (n ² ) времева сложност и 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, ние се фокусираме върху намирането на най-малката стойност в масива, за да завършим сортирането. Ето стъпка по стъпка разбивка на това как работи Сортирането на селекцията:

• Приемаме първия елемент в масива като най-малкия.
• Сравняваме този елемент със следващия елемент в масива.
• Ако следващият елемент е по-малък от този в момента, ние задаваме следващия елемент като новата най-малка стойност.
• Продължаваме да повтаряме тези стъпки, докато стигнем до края на масива.
• Когато намерим стойност в масива, която е по-малка от тази, с която започнахме, разменяме техните позиции.
• Продължаваме да правим сравненията и да преминем към следващия елемент. Докато не се подреди целият масив.

Точно като алгоритъма за сортиране на балончета, сортировката за избор има сложност на O (n ² ) и сложност на пространството 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. Обединяване алгоритъм за сортиране

Подобно на Сортирането и сортирането на балони, сортирането на сливане е един от популярните алгоритми за сортиране в компютърните науки, можете да го внедрите в повечето езици за програмиране и има добри резултати, без да е твърде нуждаещ се от ресурси.

Сливане Сортиране използва метода Разделяне и завладяване, за да сортира масив или произволен списък от елементи. Терминът разделя и завладява означава, че разделяме един голям проблем на няколко по-малки проблема и тогава решаваме тези малки проблеми. След като се разрешат по-малките проблеми, ние комбинираме резултатите, които водят до решението на големия проблем.

Разбирането на алгоритъма всъщност е просто:

• Разделяме дадения масив на 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 е един от най-ефективните начини за сортиране на елементи в компютърните системи. Similor за сливане на сорта, Quicksort работи върху алгоритъма на разделяне и завладяване. В този случай ние намираме въртящ елемент в масива, за да сравним всички други масиви от елементи и след това преместваме елементите по начин, при който всички елементи преди избраните ни въртящи елементи са по-малки и всички елементи след въртящия се елемент са с по-големи размери. След като направим това, ключът е да продължаваме да го правим многократно и ще разполагаме със сортирания масив.

Следват стъпките, които могат да бъдат следвани за прилагане на алгоритъм за бързо спиране:

• Избираме елемент от масива и го наричаме „Pivot Point“
• Започваме указател, наречен ляв показалец, от който е на първия елемент в масива.
• По подобен начин стартираме указател, наречен десен указател при последния елемент в масива.
• Ако стойността на елемента в левия показалец е по-малка в сравнение с избраната точка на въртене, преместваме левия показалец наляво (добавяме +1 към него) и продължаваме да го повтаряме, докато стойността в левия показалец не се окаже по-голяма от стойност на точката на въртене или равна на нея.
• Ако стойността на елемента в десния показалец в списъка е по-висока от стойността на въртящия се елемент, ние монтираме десния показалец наляво. Повторете това, докато стойността вдясно показалеца е по-ниска от (или равна на) стойността на въртене.
• Когато стойността на левия показалец е по-малка или равна на стойността на десния показалец, сменете стойностите.
• Преместете десния показалец наляво от един, левия показалец надясно от един.
• Повторете, докато левите и десните указатели не се срещнат.

Код:

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. Алгоритъм за сортиране на купчина

Сортирането в Heap е начин за сортиране на елементи чрез използване на структурата на данните „Heap“. Методът е доста подобен на техниката за подбор на сортиране, която обсъждахме по-рано. Сега може би се чудите за Heaps и как са дефинирани, преди да стигнете до алгоритъма, първо да разберем купища.

С две думи, грамада е бинарно дърво с някои добавени правила. Едно правило гласи, че в купчина, дървото трябва да бъде пълно двоично дърво, което просто означава, че е необходимо да се запълнят всички възли на текущото ниво, преди да се добави друг. Следващото правило за купчината е, че трябва да има определена връзка дете и родител със стойностите на елементите на купчината.

В мин. Купчина стойността на родител трябва да е по-малка от неговите деца. В максимална грамада, както се досещате, стойността на родителя трябва да е по-голяма от неговата дете.

Сега, когато дефинициите не са на път, нека да разгледаме как работи купчина:

• Първо изграждаме максимална грамада, която гарантира, че елементът с най-висока стойност е в горната част.
• Превключваме горния елемент с последния елемент от купчината и изваждаме горния елемент от купището и го съхраняваме в сортиран масив.
• Продължаваме да повтаряме стъпка първа и две, докато в грамадата остава само един елемент.

Едно нещо, което трябва да се има предвид, е, че Heaps не се поддържа от самото начало в JavaScript, следователно трябва да прибягваме до внедряването на Heaps, използвайки масиви. Космическата сложност на сортирането на купчината е 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 алгоритми за сортиране в javas, заедно с примери и внедряване на код. Можете също да разгледате следните статии, за да научите повече -

1. JavaScript Компилатори
2. Обратно в JavaScript
3. Въведение в JavaScript
4. Квадрати в Java
5. Бързо сортиране на алгоритми в Java
6. Масиви в структурата на данните
7. C ++ Алгоритъм | Примери за C ++ алгоритъм