Проектите за разработка използват различни алгоритми по-често, отколкото си мислите. Да предположим например, че трябва да сортираме някои данни по определени параметри (колони), за да можем да навигираме в данните без много усorя. Така че изобщо не би било странно интервюиращият за работа да ви попита за конкретен основен алгоритъм и може би да даде задача да го внедри с помощта на code. И тъй като сте на този уебсайт, ще бъда толкова смел да предположа, че пишете на Java. Ето защо днес ви предлагам да се запознаете с някои основни алгоритми и конкретни примери How да ги внедрите в Java. Под „някои“ имам предвид:
Преглед на алгоритмите за сортиране на масиви:
сортиране на мехурчета,
сортиране на селекцията,
сортиране на вмъкване,
Сортиране на черупки,
бързо сортиране,
сортиране чрез сливане,
Алчни алгоритми
Алгоритми за намиране на пътя
първо търсене в дълбочина
търсене в широчината
Алгоритъмът на Дейкстра за най-краткия път първи
Е, без повече шум, нека да се заемем с работата.
1. Преглед на алгоритмите за сортиране
Сортиране на мехурчета
Този алгоритъм за сортиране е известен предимно със своята простота, но е и един от най-бавните. Като пример, нека разгледаме балонно сортиране за числа във възходящ ред. Нека си представим произволна последователност от числа. Ще изпълним следните стъпки върху тези числа, започвайки от началото на последователността:
сравнете две числа;
ако числото отляво е по-голямо, разменете ги;
преместете една позиция надясно.
След като извършим тези стъпки върху цялата последователност, ще открием, че най-голямото число е в края на нашата серия от числа. След това правим още едно преминаване през последователността, изпълнявайки точно същите стъпки като по-горе. Но този път няма да включим последния елемент от списъка, тъй като той е най-голямото число и вече точно където трябва да бъде, когато числата се сортират. Още веднъж ще преместим следващото най-голямо число в края на нашата последователност. Разбира се, това означава, че двете най-големи числа стоят на правилните си места. Отново преминаваме през последователността, като изключваме елементите, които вече са на местата си, докато всички елементи са в необходимия ред. Нека да разгледаме How балонното сортиране е реализирано в codeа на Java:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6,3,8,2,6,9,4,11,1};
bubbleSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void bubbleSort(int[] array) {
for(int i = array.length -1; i > 1; i--) {
for (int j = 0; j < i; j++) { //
if (array[j] > array[j+1]) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
}
Както можете да видите, тук няма нищо сложно. Всичко изглежда просто страхотно и би било така, ако не беше един недостатък — сортирането на мехурчета е много, много бавно. Сложността на времето е O(N²), тъй като имаме вложени цикли. Външният цикъл над елементите се изпълнява N пъти. Вътрешният цикъл също се изпълнява N пъти. В резултат на това получаваме N*N or N² итерации.
Сортиране на селекцията
Този алгоритъм е подобен на балонно сортиране, но работи малко по-бързо. Отново, като пример, нека вземем поредица от числа, които искаме да подредим във възходящ ред. Същността на този алгоритъм е да преминем последователно през всички числа и да изберем най-малкия елемент, който вземаме и разменяме с най-левия елемент (0-ия елемент). Тук имаме ситуация, подобна на балонното сортиране, но в този случай нашият сортиран елемент ще бъде най-малкият. Следователно следващото преминаване през елементите ще започне от елемента с индекс 1. Ще повтаряме тези преминавания, докато всички елементи бъдат сортирани. Внедряване в Java:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 2, 6, 9, 4, 11, 1};
sortBySelect(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void sortBySelect(int[] array) {
for (int i = 0; i < array.length-1; i++) { // An ordinary outer loop
int min = i;
for (int j = i + 1; j < array.length; j++) { // An ordinary loop, but one that accounts for the sorted numbers
if (array[j] < array[min]) {
min = j;
}
}
int temp = array[i]; // Put the sorted number in the proper cell
array[i] = array[min];
array[min] = temp;
}
}
}
Този алгоритъм е по-добър от балонното сортиране, тъй като тук броят на необходимите смени е намален от O(N²) на O(N). Не прекарваме един елемент през целия списък, но броят на сравненията все още е O(N²).
Сортиране на вмъкване
Разглеждаме още една числова последователност, която искаме да подредим във възходящ ред. Този алгоритъм се състои в поставяне на маркер, където всички елементи отляво на маркера вече са частично сортирани помежду си. На всяка стъпка от алгоритъма един от елементите ще бъде избран и поставен на желаната позиция в частично сортираната последователност. По този начин сортираната част ще расте, докато не бъдат прегледани всички елементи. Чудите ли се How получавате подмножеството от елементи, които вече са сортирани и How определяме къде да поставим маркера? Но масивът, съставен от първия елемент, вече е сортиран, нали? Нека да разгледаме имплементацията в Java:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
insertionSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void insertionSort(int[] array) {
for (int i = 1; i < array.length; i++) { // i is the dividing marker
int temp = array[i]; // Make a temporary copy of the marked element
int j = i;
while (j > 0 && array[j - 1] >= temp) { // Until a smaller element is found
array[j] = array[j - 1]; // We shift the element to the right
--j;
}
array[j] = temp; // Insert the marked element in its proper place
}
}
}
Този тип сортиране е по-добър от описаните по-горе, тъй като въпреки факта, че има същото време за работа O(N²), този алгоритъм е два пъти по-бърз от балонното сортиране и малко по-бърз от сортирането със селекцията.
Сортиране на черупки
Това сортиране е по същество модифицирано сортиране на вмъкване. за Howво говоря Нека поставим първите неща на първо място. Първо трябва да изберем интервал. Има много подходи за извършване на този избор. Няма да навлизаме в много подробности за това. Нека разделим нашия масив наполовина и да получим няHowво число — това ще бъде нашият интервал. Така че, ако имаме 9 елемента в нашия масив, тогава нашият интервал ще бъде 9/2 = 4,5. Изхвърляме дробната част и получаваме 4, тъй като индексите на масива могат да бъдат само цели числа. Ще използваме този интервал, за да сформираме нашите групи. Ако даден елемент има индекс 0, то индексът на следващия елемент в неговата група е 0+4, тоест 4. Третият елемент ще има индекс 4+4, четвъртият — 8+4 и т.н. Във втора група първият елемент ще бъде 1,5,9... В трета и четвърта група ситуацията ще бъде същата. Като резултат, от числовия масив {6,3,8,8,6,9,4,11,1} получаваме четири групи: I — {6,6,1} II — {3,9} III — {8,4 } IV — {8,11} Те запазват местата си в общия масив, но сме маркирали като членове на една и съща група: {6,3,8,8,6,9,4,11,1} След това вмъкване sort се прилага към тези групи и тогава те изглеждат така: I — {1,6,6} II — {3,9} III — {4,8} IV — {8,11} В общия масив клетките, заети от групите, ще останат същите, но техният вътрешен ред ще се промени според реда на групите по-горе: {1,3,4,8,6,9,8,11,6} Масивът е станал малко по-подредено, нали? Следващият интервал ще бъде разделен на 2: 4/2 = 2 Имаме две групи: I — {1,4,6,8,6} II — {3,8,9,11} В общия масив имаме : {1,3,4,8,6,9,8,11,6} Изпълняваме алгоритъма за сортиране чрез вмъкване на двете групи и получаваме този масив: {1,3,4,8,6,9,6, 11, 8} Сега нашият масив е почти сортиран. Трябва да извършим последна итерация на алгоритъма: разделяме интервала на 2: 2/2 = 1. Получаваме група, съставена от целия масив: {1,3,4,8,6,9,6,11 ,8} Изпълнявайки алгоритъма за сортиране чрез вмъкване върху това, получаваме: {1,3,4,6,6,8,8,9,11} Нека да разгледаме How можем да оживим това сортиране в Java code:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
sortBySelect(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void sortBySelect(int[] array) {
int length = array.length;
int step = length / 2;
while (step > 0) {
for (int numberOfGroup = 1; numberOfGroup < length - step; numberOfGroup++) { // We pass over all of our groups
int j = numberOfGroup;
while (j >= 0 && array[j] > array[j + step]) { // Insertion sort inside the group
int temp = array[j];
array[j] = array[j + step];
array[j + step] = temp;
j--;
}
}
step = step / 2; // Shrink the interval
}
}
}
В момента не е лесно да се характеризира представянето на Shellsort, тъй като резултатите се различават в различните ситуации. Експерименталните оценки варират от O(N 3/2 ) до O(N 7/6 ).
Бързо сортиране
Това е един от най-популярните алгоритми, така че си струва да му обърнете специално внимание. Същността на този алгоритъм е, че осевият елемент се избира в списък с елементи. Сортираме всички останали елементи спрямо основния елемент. Стойностите, по-малки от основния елемент, са отляво. Стойностите, по-големи от него, са вдясно. След това осевите елементи също се избират в дясната и лявата част и се случва същото: стойностите се сортират спрямо тези елементи. След това се избират осеви елементи в новоформираните части и така нататък, докато получим сортирана последователност. Следната реализация на Java на този алгоритъм използва рекурсия:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
fastSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void fastSort(int[] array) {
recursionFastSort(array, 0, array.length - 1);
}
public static void recursionFastSort(int[] array, int min, int max) {
if (array.length == 0) // Condition for exiting recursion if the array length is 0
return;
if (min> = max) // Terminate the recursion, since there is nothing to divide
return;
int middle = min + (max - min) / 2; // Select the middle
int middleElement = array[middle];
int i = min, j = max;
while (i <= j) { // Every element less than the middle element will be to the left, and large ones will be to the right
while (array[i] < middleElement) {
i++;
}
while (array[j] > middleElement) {
j--;
}
if (i <= j) { // Swap places
int temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
}
if (min < j) // Make a recursive call on the elements that are less than middle
recursionFastSort(array, min, j);
if (max > i) // Make a recursive call on the elements larger than middle
recursionFastSort(array, i, max);
}
}
Без съмнение алгоритъмът за бързо сортиране е най-популярен, тъй като в повечето ситуации работи по-бързо от други. Времевата му сложност е O(N*logN).
Сортиране чрез сливане
Този сорт също е популярен. Това е един от многото алгоритми, които разчитат на принципа "разделяй и владей". Такива алгоритми първо разделят проблема на управляеми части (бързото сортиране е друг пример за такъв алгоритъм). И така, Howва е същността на този алгоритъм?
Разделям:
Масивът е разделен на две части с приблизително еднакъв размер. Всяка от тези две части се разделя на още две и така докато останат възможно най-малките неделими части. Най-малките неделими части имаме, когато всеки масив има един елемент, т.е. масив, който вече е сортиран.
Покори:
Това е мястото, където започваме процеса, който даде името на алгоритъма: сливане. За целта вземаме двата получени сортирани масива и ги обединяваме в един. В този случай най-малкият от първите елементи на двата масива се записва в получения масив. Тази операция се повтаря, докато всички елементи в тези два масива бъдат копирани. Тоест, ако имаме два минимални масива {6} и {4}, сравняваме техните стойности и генерираме този обединен резултат: {4,6}. Ако имаме сортирани масиви {4,6} и {2,8}, първо сравняваме стойностите 4 и 2 и след това записваме 2 в получения масив. След това 4 и 8 ще бъдат сравнени и ще напишем 4. Накрая ще бъдат сравнени 6 и 8. Съответно ще напишем 6 и едва след това ще напишем 8. В резултат на това получаваме следния обединен масив: {2,4,6,8}. Как ще изглежда това в codeа на Java? За да стартираме този алгоритъм, ще ни е удобно да използваме рекурсия:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
testArr = mergeSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static int[] mergeSort(int[] array1) {
int[] sortArr = Arrays.copyOf(array1, array1.length); // Array for sorting
int[] bufferArr = new int[array1.length];// Buffer array
return recursionMergeSort(sortArr, bufferArr, 0, array1.length);
}
public static int[] recursionMergeSort(int[] sortArr, int[] bufferArr,
int startIndex, int endIndex) {
if (startIndex> = endIndex - 1) { // Return the array when there is only one element left in the array range under consideration
return sortArr;
}
// Make a recursive call to get two sorted arrays:
int middle = startIndex + (endIndex - startIndex) / 2;
int[] firstSortArr = recursionMergeSort(sortArr, bufferArr, startIndex, middle);
int[] secondSortArr = recursionMergeSort(sortArr, bufferArr, middle, endIndex);
// Merge the sorted arrays:
int firstIndex = startIndex;
int secondIndex = middle;
int destIndex = startIndex;
int[] result = firstSortArr == sortArr ? bufferArr : sortArr;
while (firstIndex < middle && secondIndex < endIndex) {
result[destIndex++] = firstSortArr[firstIndex] < secondSortArr[secondIndex]
? firstSortArr[firstIndex++] : secondSortArr[secondIndex++];
}
while (firstIndex < middle) {
result[destIndex++] = firstSortArr[firstIndex++];
}
while (secondIndex < endIndex) {
result[destIndex++] = secondSortArr[secondIndex++];
}
return result;
}
}
Както при бързото сортиране, преместваме рекурсивния метод в междинен метод, така че потребителят трябва само да предостави масива за сортиране и не трябва да се притеснява за предоставянето на допълнителни аргументи по подразбиране. Този алгоритъм има прorки с бързото сортиране и не е изненадващо, че скоростта му на изпълнение е същата: O(N*logN).
2. Алчни алгоритми
Алчният алгоритъм е подход, при който на всеки етап се вземат локално оптимални решения, като се допуска, че крайното решение също ще бъде оптимално. „Оптималното“ решение ще бъде това, което предлага най-очевидната и незабавна полза на всяка конкретна стъпка/етап. За да проучим този алгоритъм, нека вземем един доста често срещан проблем — проблемът с раницата. Престорете се за момент, че сте крадец. Разбor сте магазин през нощта с раница (раница). Пред вас има няколко стоки, които можете да откраднете. Но в същото време вашата раница е с ограничен капацитет. Може да носи не повече от 30 единици тегло. Също така искате да вземете най-ценния набор от стоки, които ще се поберат в раницата. Как определяте Howво да сложите в чантата си? Така,
Изберете най-скъпия артикул, който все още не е взет.
Ако се побира в раницата, сложете го. Ако не, оставете го.
Откраднахме ли вече всичко? Ако не, връщаме се на стъпка 1. Ако да, тогава правим бързо бягство от магазина, тъй като сме постигнали това, за което сме дошли.
Нека да разгледаме това, но в Java. Ето How ще изглежда класът Item:
public class Item implements Comparable {
private String name;
private int weight;
private int value;
public Item(String name, int weight, int value) {
this.name = name;
this.weight = weight;
this.value = value;
}
public String getName() {
return name;
}
public int getWeight() {
return weight;
}
public int getValue() {
return value;
}
@Override
public int compareTo(Item o) {
return this.value > o.value ? -1 : 1;
}
}
Тук няма нищо особено: три полета (име, тегло, стойност), които определят характеристиките на артикула. Освен това, Howто можете да видите, Comparable интерфейсът е внедрен, за да ни позволи да сортираме нашите артикули по цена. След това ще разгледаме класа Bag, който представлява нашата раница:
public class Bag {
private final int maxWeight;
private List<Item> items;
private int currentWeight;
private int currentValue;
public Bag(int maxWeight) {
this.maxWeight = maxWeight;
items = new ArrayList<>();
currentValue = 0;
}
public int getMaxWeight() {
return maxWeight;
}
public int getCurrentValue() {
return currentValue;
}
public int getCurrentWeight() {
return currentWeight;
}
public void addItem(Item item) {
items.add(item);
currentWeight += item.getWeight();
currentValue += item.getValue();
}
}
maxWeight е капацитетът на нашата раница, който се задава, когато създаваме обект;
items представлява предметите в нашата раница;
currentWeight , currentValue — тези полета съхраняват текущото тегло и стойност на всички артикули в раницата, които увеличаваме, когато добавим нов артикул в метода addItem.
Както и да е, нека сега да отидем в класа, където се развиват всички действия:
public class Solution {
public static void main(String[] args) {
List<Item> items = new ArrayList<>();
items.add(new Item("Guitar", 7, 800));
items.add(new Item("Iron", 6, 500));
items.add(new Item("Tea pot", 3, 300));
items.add(new Item("Lamp", 4, 500));
items.add(new Item("Television", 15, 2000));
items.add(new Item("Vase", 2, 450));
items.add(new Item("Mixer", 2, 400));
items.add(new Item("Blender", 3, 200));
Collections.sort(items);
Bag firstBag = new Bag(30);
fillBackpack(firstBag, items);
System.out.println("Knapsack weight is " + firstBag.getCurrentWeight() +
". The total value of items in the knapsack is " + firstBag.getCurrentValue());
}
}
Първо създаваме списък с елементи и го сортираме. Ние създаваме чанта с капацитет 30 единици. След това предаваме артикулите и обекта на чантата на метода fillBackpack, който запълва раницата според нашия алчен алгоритъм:
Доста е просто: започваме да разглеждаме списък с артикули, сортирани по цена, и да ги поставяме в чантата, ако капацитетът й позволява. Ако няма достатъчно място, тогава елементът ще бъде пропуснат и ние ще продължим да преглеждаме останалите елементи, докато стигнем до края на списъка. След като стартираме main, ето изхода от конзолата, който ще получим:
Tagлото на раницата е 29. Общата стойност на артикулите в раницата е 3700
Това е пример за алчен алгоритъм: на всяка стъпка се избира локално оптимално решение и в крайна сметка получавате глобално оптимално решение. В нашия случай най-добрият вариант е най-скъпият артикул. Но дали това е най-доброто решение? Не мислите ли, че е възможно леко да подобрим нашето решение, за да напълним раницата си с предмети, които имат още по-голяма обща стойност? Нека да разгледаме How може да стане това.
public static void effectiveFillBackpack(Bag bag, List items) {
Map<Double, Item> sortByRatio = new TreeMap(Collections.reverseOrder());
for (Item item : items) {
sortByRatio.put((double)item.getValue() / item.getWeight(), item);
}
for (Map.Entry<Double, Item> entry : sortByRatio.entrySet()) {
if(bag.getMaxWeight() > bag.getCurrentWeight() + entry.getValue().getWeight()) {
bag.addItem(entry.getValue());
}
}
}
Тук първо изчисляваме съотношението стойност/тегло за всеки артикул. Това ни казва стойността на всяка единица от даден артикул. И след това използваме тези съотношения, за да сортираме артикулите си и да ги добавим в чантата си. Нека изпълним следното:
Bag secondBag = new Bag(30);
effectiveFillBackpack(secondBag, items);
System.out.println("The weight of the knapsack is " + secondBag.getCurrentWeight() +
". The total cost of items in the knapsack is " + secondBag.getCurrentValue());
Получаваме този конзолен изход:
Tagлото на раницата е 29. Общата цена на артикулите в раницата е 4150
Малко по-добре, нали? Алчният алгоритъм прави локално оптимален избор на всяка стъпка, надявайки се, че крайното решение също ще бъде оптимално. Това предположение не винаги е валидно, но за много задачи алчните алгоритми наистина дават оптимално крайно решение. Времевата сложност на този алгоритъм е O(N). Доста добре, а?
И тъй като сте на този уебсайт, ще бъда толкова смел да предположа, че пишете на Java. Ето защо днес ви предлагам да се запознаете с някои основни алгоритми и конкретни примери How да ги внедрите в Java. Под „някои“ имам предвид:
GO TO FULL VERSION