Сортирането е една от основните операции, които извършваме върху обекти. Дори в детството децата се учат да сортират, докато развиват своите мисловни умения. Компютрите и софтуерът не са изключение. В Java има огромно разнообразие от алгоритми за сортиране . Предлагам ви да проверите Howви са те и How работят. Ами ако ви попитат за някой от тях на интервю някой ден?
Въведение
Сортирането на елементи е една от категориите алгоритми, които разработчикът трябва да знае. Ако компютърните науки някога не се приемаха сериозно, когато бях в учorще, днешните ученици трябва да могат да прилагат и разбират алгоритми за сортиране. Основните алгоритми, най-простите, се изпълняват с помощта на for цикъл. Естествено, за да сортирате колекция от елементи, като например масив, трябва по няHowъв начин да преминете през колекцията. Например:
int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
Какво може да се каже за този сегмент от code? Имаме цикъл, в който променяме индекса ( int i) от 0 до последния елемент в масива. Всъщност ние просто вземаме всеки елемент от масива и отпечатваме съдържанието му. Колкото повече елементи има в масива, толкова повече време ще отнеме завършването на codeа. Тоест, ако nе броят на елементите, кога n = 10изпълнението на програмата ще отнеме два пъти повече време, отколкото когато n = 5. Ако нашата програма има единичен цикъл, времето за изпълнение нараства линейно: колкото повече елементи има, толкова по-дълго е времето за изпълнение. Оказва се, че алгоритъмът по-горе работи в линейно време (линейна функция на n). В такива случаи казваме, че сложността на алгоритъма е "O(n)". Тази нотация се нарича още "голямо О" or "асимптотично поведение". Но можете просто да си спомните "
Най-простият алгоритъм за сортиране (балонно сортиране)
Да предположим, че имаме масив и можем да итерираме през него. Страхотен. Сега нека се опитаме да го сортираме във възходящ ред. Какво означава това? Това означава, че дадени два елемента (например, a = 6, b = 5), трябва да пренаредим aи bако aе по-голямо от b(ако a > b). Какво означава това, когато използваме индекс за работа с колекция (Howъвто е случаят с масив)? Това означава, че ако елементът с индекс a е по-голям от елемента с индекс b( array[a] > array[b]), тогава елементите трябва да бъдат разменени. Има различни начини за смяна на местата. Но ние ще използваме техника, която е проста, разбираема и лесна за запомняне:
private void swap(int[] array, int ind1, int ind2) {
int tmp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = tmp;
}
Сега можем да напишем следното:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
}
}
System.out.println(Arrays.toString(array));
Както можете да видите, елементите наистина са разменени. Започнахме с индекс 1, защото ако масивът има само един елемент, изразът array[i] < array[i-1]е невалиден за индекс 0. Правейки това също ни предпазва от случаи, когато масивът няма елементи or има само един елемент, и прави codeа да изглежда по-добре. Но полученият масив все още не е сортиран, защото едно преминаване не е достатъчно, за да се извърши сортирането. Ще трябва да добавим още един цикъл, в който ще извършваме преминавания отново и отново, докато получим сортиран масив:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
boolean needIteration = true;
while (needIteration) {
needIteration = false;
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
needIteration = true;
}
}
}
System.out.println(Arrays.toString(array));
Така завършихме нашия първи алгоритъм за сортиране. Повтаряме външния цикъл ( while), докато решим, че не са необходими повече итерации. По подразбиране, преди всяка нова итерация, ние приемаме, че нашият масив е сортиран и не е необходимо да правим цикъл повече. Съответно преминаваме последователно през елементите и проверяваме това предположение. Но ако елементите не са в ред, тогава ние разменяме елементи и разбираме, че сега нямаме гаранция, че елементите са в правилния ред. Това означава, че трябва да извършим още една итерация. Да предположим например, че имаме [3, 5, 2]. 5е повече от 3— всичко е наред. Но 2е по-малко от 5. Въпреки това, [3, 2, 5]изисква още един пропуск, тъй като3 > 2и те трябва да се сменят. Тъй като използваме цикъл в цикъл, сложността на нашия алгоритъм се увеличава. Дадени елементи nстава n * n, т.е. O(n^2)Това се нарича квадратична сложност. Като цяло не можем да знаем точно колко итерации ще са необходими. Изразът на сложност на алгоритъм показва How сложността се увеличава в най-лошия случай. Тоест, той показва колко ще се увеличи времето за изпълнение с nпромяна на броя на елементите. Bubble sort е един от най-простите и неефективни алгоритми за сортиране. Понякога се нарича и "глупав вид". Материал по тази тема:
Друг алгоритъм за сортиране е сортирането по избор. Той също има квадратична сложност, но повече за това по-късно. Така че идеята е проста. При всяко преминаване избираме най-малкия елемент и го преместваме в началото. Освен това всяко преминаване започва една стъпка надясно. С други думи, първото преминаване започва от нулевия елемент, второто преминаване от първото и т.н. Ще изглежда така:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
int minInd = left;
for (int i = left; i < array.length; i++) {
if (array[i] < array[minInd]) {
minInd = i;
}
}
swap(array, left, minInd);
}
System.out.println(Arrays.toString(array));
Това сортиране е нестабилно, тъй като идентични елементи (по отношение на характеристиките, които използваме за сортиране на елементите) могат да променят относителните си позиции. Има добър пример в статията в Уикипедия за сортиране при избор . Материал по тази тема:
Сортирането чрез вмъкване също има квадратична сложност, тъй като отново имаме цикъл в цикъл. Какво прави сортирането при вмъкване различно? Този алгоритъм за сортиране е "стабилен". Това означава, че идентични елементи няма да променят своя относителен ред. Отново имаме предвид идентични по отношение на характеристиките, по които сортираме.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
// Get an element
int value = array[left];
// Iterate through the elements that are in front of this element
int i = left - 1;
for (; i >= 0; i--) {
// If the current element is smaller, then move the larger element to the right.
if (value < array[i]) {
array[i + 1] = array[i];
} else {
// If the current element is larger, we stop
break;
}
}
// Insert the current value in the empty space
array[i + 1] = value;
}
System.out.println(Arrays.toString(array));
Сортиране на совалка
Има друг прост алгоритъм за сортиране: совалково сортиране. Това е известно още като сортиране на двупосочни мехурчета or сортиране на шейкър за коктейли. Тези алтернативни имена ни казват, че сортът совалка не е за космическата совалка. Става въпрос за нещо, което се движи напред-назад. Сега можете да мислите за това, когато мислите за този алгоритъм. Каква е същността на алгоритъма? Същността на алгоритъма е, че итерираме отляво надясно, разменяйки елементите и проверявайки дали някой от елементите, останали в другата посока, трябва да бъде разменен.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i - 1);
for (int z = i - 1; (z - 1) >= 0; z--) {
if (array[z] < array[z - 1]) {
swap(array, z, z - 1);
} else {
break;
}
}
}
}
System.out.println(Arrays.toString(array));
Друг прост алгоритъм за сортиране е shell sort. Същността му е подобна на балонното сортиране, но във всяка итерация имаме различна празнина между сравняваните елементи. Нарязва се наполовина при всяка итерация. Ето една реализация:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
// Calculate the gap between the checked elements
int gap = array.length / 2;
// As long as there is a gap between the elements
while (gap >= 1) {
for (int right = 0; right < array.length; right++) {
// Shift the right index until we find one for which
// there is the necessary gap between it and the element before it
for (int c = right - gap; c >= 0; c -= gap) {
if (array[c] > array[c + gap]) {
swap(array, c, c + gap);
}
}
}
// Recalculate the gap
gap = gap / 2;
}
System.out.println(Arrays.toString(array));
В допълнение към тези прости алгоритми за сортиране има и по-сложни алгоритми за сортиране. Например сортиране чрез сливане. Трябва да се отбележат две неща. Първо, рекурсията ни идва на помощ тук. Второ, сложността на алгоритъма вече не е квадратична, Howто сме свикнали. Сложността на този алгоритъм е логаритмична. Това е написано като O(n log n). Така че нека го приложим. Първо, ще напишем рекурсивно извикване на метода за сортиране:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
}
Сега нека добавим основното действие към нашата реализация. Ето нашия супер метод:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
// Create a temporary array with the required size
int[] buffer = new int[right - left + 1];
// Starting from the specified left index, go through each element.
int cursor = left;
for (int i = 0; i < buffer.length; i++) {
// We use delimeter to point to the element on the right half
// If delimeter> right, then the right half has no elements that haven't been added
if (delimiter > right || source[cursor] > source[delimiter]) {
buffer[i] = source[cursor];
cursor++;
} else {
buffer[i] = source[delimiter];
delimiter++;
}
}
System.arraycopy(buffer, 0, source, left, buffer.length);
}
Можем да изпълним нашия пример, като извикамеmergeSort(array, 0, array.length-1). Както можете да видите, процесът се свежда до приемане на входен масив заедно с указания за началото и края на секцията, която трябва да бъде сортирана. Когато сортирането започне, това са началото и краят на масива. След това изчисляваме разделителя, който е индексът, където ще разделим масива. Ако масивът може да бъде разделен на 2 части, тогава извикваме метода за сортиране рекурсивно за двете половини на масива. Подготвяме спомагателен буфер, където ще вмъкнем сортирания раздел. След това задайте индекса в началото на секцията, която ще сортирате, и започнете да преминавате през всеки елемент от празния буфер, като го запълвате с най-малките елементи. Ако елементът, към който сочи индексът, е по-малък от елемента, към който сочи разделителят, поставяме елемента в буфера и изместваме индекса. В противен случай, поставяме елемента, към който сочи разделителят, в буфера и изместваме разделителя. Веднага щом разделителят излезе извън границите на сортирания раздел or запълним целия масив, посоченият диапазон се счита за сортиран.Материал по тази тема:
Друг интересен алгоритъм за сортиране е сортирането с броене. Алгоритмичната сложност тук е O(n+k), където nе броят на елементите и kе максималната стойност на елемент. Този алгоритъм има един недостатък: трябва да знаем минималните и максималните стойности в масива. Ето пример за сортиране на броенето:
public static int[] countingSort(int[] theArray, int maxValue) {
// An array of "counters", ranging from 0 to the maximum value
int numCounts[] = new int[maxValue + 1];
// We increase the counter in the corresponding cell (index = value)
for (int num : theArray) {
numCounts[num]++;
}
// Create an array to hold the sorted result
int[] sortedArray = new int[theArray.length];
int currentSortedIndex = 0;
// Run through the array of "counters"
for (int n = 0; n < numCounts.length; n++) {
int count = numCounts[n];
// Run through the number of values
for (int k = 0; k < count; k++) {
sortedArray[currentSortedIndex] = n;
currentSortedIndex++;
}
}
return sortedArray;
}
Разбирате, че е много неудобно, когато трябва да знаем предварително минималните и максималните стойности. И имаме друг алгоритъм тук: радикално сортиране. Ще представя алгоритъма тук само визуално. Вижте допълнителните материали за изпълнението: Материали:
Е, време е за десерт — бързо сортиране, един от най-известните алгоритми за сортиране. Има логаритмична сложност: O(n log n). Този алгоритъм за сортиране е разработен от Tony Hoare. Интересното е, че той го изобретява, докато живее в Съветския съюз, където учи машинен превод в Московския университет и разработва руско-английски разговорник. Нещо повече, Java използва по-сложна version на този алгоритъм в Arrays.sort. Collections.sortHowво за Защо не погледнете How са подредени нещата "под капака"? Ето codeа:
public static void quickSort(int[] source, int leftBorder, int rightBorder) {
int leftMarker = leftBorder;
int rightMarker = rightBorder;
int pivot = source[(leftMarker + rightMarker) / 2];
do {
// Move the left marker from left to right as long as the element is less than pivot
while (source[leftMarker] < pivot) {
leftMarker++;
}
// Move the right marker as long as the element is greater than pivot
while (source[rightMarker] > pivot) {
rightMarker--;
}
// Check whether we need to swap the elements pointed to by the markers
if (leftMarker <= rightMarker) {
// The left marker will be less than the right one only if we need to do a swap
if (leftMarker < rightMarker) {
int tmp = source[leftMarker];
source[leftMarker] = source[rightMarker];
source[rightMarker] = tmp;
}
// Shift the markers to get new borders
leftMarker++;
rightMarker--;
}
} while (leftMarker <= rightMarker);
// Execute recursively on the parts
if (leftMarker < rightBorder) {
quickSort(source, leftMarker, rightBorder);
}
if (leftBorder < rightMarker) {
quickSort(source, leftBorder, rightMarker);
}
}
Всичко това е много страшно, така че нека се заровим в него. За входен масив ( int[]източник) създаваме два маркера: ляв ( L) и десен ( R). По време на първото извикване на метод те съответстват на началото и края на масива. След това идентифицираме основния елемент, който е подходящо наречен pivot. След това нашата задача е да преместим стойности, по-малки от pivotвляво от pivot, а по-големи - вдясно. За да направим това, първо преместваме Lмаркера, докато намерим стойност, по-голяма от pivot. Ако не се намери по-малка стойност, тогава
L става равно на
pivot. След това преместваме
Rмаркера, докато намерим стойност, по-малка от
pivot. Ако не се намери по-голяма стойност,
Rстава равно на
pivot. След това, ако
Lмаркерът е преди
Rмаркера or съвпада с него, тогава се опитваме да разменим елементите, ако елементът
Lе по-малък от
Rелемента. След това се преместваме
Lнадясно с 1 и се преместваме
Rналяво с 1. Когато
Lмаркерът се премести отвъд
Rмаркера, това означава, че размяната е завършена: по-малките стойности са отляво на
pivot, по-големите стойности са отдясно на
pivot. След това извикваме същия метод за сортиране рекурсивно на подмасивите — от началото на секцията, която трябва да се сортира, до десния маркер и от левия маркер до края на секцията, която трябва да се сортира. Защо от началото до десния маркер? Защото в края на една итерация се оказва, че десният маркер се движи достатъчно, за да стане границата на лявата част. Този алгоритъм е по-сложен от обикновеното сортиране, така че е най-добре да го скицирате. Вземете бял лист и напишете: 4 2 6 7 3. След това напишете
pivotв средата, т.е. под номер 6. Оградете го. Под 4 напишете
L, а под 3 напишете
R. 4 по-малко от 6, 2 по-малко от 6. В крайна сметка се придвижваме
Lкъм
pivotпозицията, защото
Lне можем да преминем
pivot, според conditionто. Напишете отново 4 2 6 7 3. Оградете 6 (
pivot) и поставете
Lотдолу. Сега преместете
Rмаркера. 3 е по-малко от 6, така че поставете
Rмаркера върху 3. Тъй като 3 е по-малко от 6 (
pivot), изпълняваме a
swap. Запишете резултата: 4 2 3 7 6. Оградете 6, защото все още е
pivot. Маркерът
Lе на 3.
RМаркерът е на 6. Не забравяйте, че преместваме маркерите, докато
Lпремине отвъд
R. Преминете
Lкъм следващия номер. Тук бих искал да проуча две възможности: 1) случаят, когато предпоследното число е 7 и 2) случаят, когато е 1, а не 7.
Ако предпоследното число е 1: Преместете
Lмаркера на 1, защото можем да местим
Lтолкова дълго, колкото
Lмаркерът сочи към число, по-малко от
pivot. Но не можем да преместим
Rот 6, защото можем да преместим R само ако
Rмаркерът сочи към число, което е по-голямо от
pivot. Не изпълняваме a
swap, защото 1 е по-малко от 6. Напишете текущата ситуация: 4 2 3 1 6. Оградете 6 (
pivot).
Lсе измества
pivotи спира да се движи.
Rне се движи. Ние не извършваме размяна. Shift
Lи
Rс една позиция. Напишете
Rмаркера под 1.
LМаркерът е извън границите. Тъй като
Lе извън границите, не правим нищо. Но ние отново пишем 4 2 3 1, защото това е нашата лява страна, която е по-малка от
pivot(6). Изберете новото
pivotи започнете всичко отначало :)
Ако предпоследното число е 7:Преместете
Lмаркера на 7. Не можем да преместим десния маркер, защото той вече сочи към централната точка. 7 е по-голямо от
pivot, така че изпълняваме
swap. Запишете резултата: 4 2 3 6 7. Оградете 6, защото това е
pivot. Сега маркерът
Lе преместен на 7, а
Rмаркерът е изместен на 3. Няма смисъл да сортирате частта от
Lкъм края, защото има само 1 елемент. Частта от 4 обаче изпращаме на
Rмаркера за сортиране. Избираме a
pivotи започваме всичко отначало :) На пръв поглед може да изглежда, че ако добавите много стойности, равни на
pivot, тогава ще нарушите алгоритъма. Но това не е така. Можете да измислите сложни комбинации и на хартия да се убедите, че всичко е правилно и да се чудите, че такива прости действия прилагат толкова надежден механизъм за сортиране. Единственият недостатък е, че този алгоритъм за сортиране не е стабилен. Тъй като размяната може да промени относителния ред на идентични елементи, ако един от тях се срещне преди,
pivotпреди другият елемент да бъде разменен в частта преди
pivot.
Долния ред
По-горе разгледахме "джентълменски" набор от алгоритми за сортиране, внедрени в Java. Алгоритмите обикновено са полезни, Howто от приложна гледна точка, така и по отношение на научаването How да мислим. Някои са по-прости, други по-сложни. Умните хора защитиха дисертации за някои. За други са написали супер дебели книги. Надявам се, че допълнителните материали ще ви помогнат да научите още повече, тъй като тази статия е само преглед, който вече се оказа тежък. И целта му е да предостави кратко въведение. Можете също така да намерите въведение в алгоритмите, ако прочетете
„Алгоритми на Grokking “. Харесвам и плейлиста от Jack Brown:
AQA Decision 1 1.01 Tracing an Algorithm . За забавление можете да видите визуализации на алгоритъм при
сортиране.visualgo.net .
GO TO FULL VERSION