Udviklingsprojekter bruger forskellige algoritmer oftere, end du måske tror. Antag for eksempel, at vi skal sortere nogle data efter bestemte parametre (kolonner), så vi kan navigere gennem dataene uden stor indsats. Så det ville slet ikke være mærkeligt for en jobinterviewer at spørge dig om en bestemt grundlæggende algoritme og måske give den opgave at implementere den ved hjælp af kode. Og da du er på denne hjemmeside, vil jeg være så dristig at antage, at du skriver i Java. Derfor foreslår jeg i dag, at du gør dig bekendt med nogle grundlæggende algoritmer og med specifikke eksempler på, hvordan du implementerer dem i Java. Med "nogle" mener jeg:
Oversigt over array-sorteringsalgoritmer:
boble sortering,
udvælgelsessortering,
indsættelsessortering,
Skal sortering,
quicksort,
flette sortering,
Grådige algoritmer
Stifindende algoritmer
dybde-første søgning
bredde-første søgning
Dijkstra's Shortest Path First-algoritme
Nå, uden videre, lad os komme i gang.
1. Oversigt over sorteringsalgoritmer
Boble sortering
Denne sorteringsalgoritme er først og fremmest kendt for sin enkelhed, men den er også en af de langsomste. Lad os som et eksempel overveje en boblesortering for tal i stigende rækkefølge. Lad os forestille os en tilfældig række af tal. Vi udfører følgende trin på disse tal, startende fra begyndelsen af sekvensen:
sammenligne to tal;
hvis tallet til venstre er større, så skift dem;
flytte en position til højre.
Efter at have udført disse trin på hele sekvensen, vil vi opdage, at det største tal er i slutningen af vores talserie. Så laver vi endnu en gang over sekvensen og udfører nøjagtig de samme trin som ovenfor. Men denne gang vil vi ikke inkludere det sidste element på listen, da det er det største tal og allerede præcis hvor det skal være, når tallene sorteres. Igen ender vi med at flytte det næststørste tal til slutningen af vores sekvens. Det betyder selvfølgelig, at de to største numre står på deres rette pladser. Igen går vi over sekvensen, ekskluderer de elementer, der allerede er på deres pladser, indtil alle elementerne er i den påkrævede rækkefølge. Lad os tage et kig på, hvordan boblesortering er implementeret i Java-kode:
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;
}
}
}
}
}
Som du kan se, er der ikke noget kompliceret her. Alt virker bare fantastisk, og det ville være, hvis ikke der var en mangel - boblesortering er meget, meget langsom. Dets tidskompleksitet er O(N²), da vi har indlejrede løkker. Den ydre sløjfe over elementerne udføres N gange. Den indre løkke udføres også N gange. Som et resultat får vi N*N, eller N², iterationer.
Udvælgelsessortering
Denne algoritme ligner boblesortering, men den virker lidt hurtigere. Lad os igen, som et eksempel, tage en række tal, som vi ønsker at arrangere i stigende rækkefølge. Essensen af denne algoritme er at sekventielt iterere gennem alle tallene og vælge det mindste element, som vi tager og bytter med elementet længst til venstre (det 0. element). Her har vi en situation, der ligner boblesortering, men i dette tilfælde vil vores sorterede element være det mindste. Derfor vil den næste gennemgang af elementerne starte fra elementet med indeks 1. Vi gentager disse gennemløb, indtil alle elementerne er blevet sorteret. Implementering i 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;
}
}
}
Denne algoritme er bedre end boblesortering, fordi antallet af nødvendige skift her reduceres fra O(N²) til O(N). Vi kører ikke ét element gennem hele listen, men antallet af sammenligninger er stadig O(N²).
Indsættelsessortering
Vi betragter endnu en talrække, som vi ønsker at arrangere i stigende rækkefølge. Denne algoritme består i at placere en markør, hvor alle elementerne til venstre for markøren allerede er delvist sorteret indbyrdes. Ved hvert trin i algoritmen vil et af elementerne blive valgt og placeret på den ønskede position i den delvist sorterede sekvens. Således vil den sorterede del vokse, indtil alle elementer er blevet undersøgt. Undrer du dig over, hvordan du får den delmængde af elementer, der allerede er sorteret, og hvordan vi bestemmer, hvor markøren skal placeres? Men arrayet bestående af det første element er allerede sorteret, er det ikke? Lad os tage et kig på implementeringen i 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
}
}
}
Denne type sortering er overlegen i forhold til dem, der er beskrevet ovenfor, for på trods af at den har samme O(N²) køretid, er denne algoritme dobbelt så hurtig som boblesortering og lidt hurtigere end udvælgelsessortering.
Skal sortering
Denne sortering er i det væsentlige en modificeret indsættelsessortering. Hvad taler jeg om? Lad os sætte det første først. Vi skal først vælge et interval. Der er mange tilgange til at træffe dette valg. Vi vil ikke gå for meget i detaljer om dette. Lad os dele vores array i to og få et tal - dette vil være vores interval. Så hvis vi har 9 elementer i vores array, så vil vores interval være 9/2 = 4,5. Vi kasserer brøkdelen og får 4, da matrixindekser kun kan være heltal. Vi vil bruge dette interval til at danne vores grupper. Hvis et element har indeks 0, så er indekset for det næste element i dets gruppe 0+4, det vil sige 4. Det tredje element vil have indekset 4+4, det fjerde - 8+4, og så videre. I den anden gruppe vil det første element være 1,5,9... I den tredje og fjerde gruppe vil situationen være den samme. Som resultat, fra talarrayet {6,3,8,8,6,9,4,11,1} får vi fire grupper: I — {6,6,1} II — {3,9} III — {8,4 } IV — {8,11} De beholder deres pladser i det generelle array, men vi har markeret som medlemmer af samme gruppe: {6,3,8,8,6,9,4,11,1} Næste, indsættelse sortering anvendes på disse grupper, og så ser de sådan ud: I — {1,6,6} II — {3,9} III — {4,8} IV — {8,11} I det generelle array, celler optaget af grupperne vil forblive den samme, men deres interne rækkefølge vil ændre sig i henhold til rækkefølgen af grupperne ovenfor: {1,3,4,8,6,9,8,11,6} Arrayet er blevet til en lidt mere bestilt, ikke? Det næste interval vil blive divideret med 2: 4/2 = 2 Vi har to grupper: I — {1,4,6,8,6} II — {3,8,9,11} I det generelle array har vi : {1,3,4,8,6,9,8,11,6} Vi kører indsættelsessorteringsalgoritmen på begge grupper og får denne matrix: {1,3,4,8,6,9,6, 11, 8} Nu er vores array næsten sorteret. Vi skal udføre en sidste iteration af algoritmen: vi dividerer intervallet med 2: 2/2 = 1. Vi får en gruppe bestående af hele arrayet: {1,3,4,8,6,9,6,11 ,8} Ved at køre indsættelsessorteringsalgoritmen på det, får vi: {1,3,4,6,6,8,8,9,11} Lad os tage et kig på, hvordan vi kan bringe denne slags ud i livet i Java-kode:
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
}
}
}
I øjeblikket er Shellsorts ydeevne ikke let at karakterisere, da resultaterne er forskellige i forskellige situationer. Eksperimentelle estimater spænder fra O(N 3/2 ) til O(N 7/6 ).
Quicksort
Dette er en af de mest populære algoritmer, så det er værd at være særlig opmærksom på. Kernen i denne algoritme er, at et pivotelement er valgt på en liste over elementer. Vi sorterer alle de andre elementer i forhold til pivotelementet. Værdier mindre end pivotelementet er til venstre. Værdier større end det er til højre. Dernæst vælges pivotelementer også i højre og venstre del, og det samme sker: Værdierne sorteres i forhold til disse elementer. Derefter vælges pivotelementer i de nydannede dele, og så videre indtil vi får en sorteret sekvens. Følgende Java-implementering af denne algoritme bruger rekursion:
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);
}
}
Uden tvivl er quicksort-algoritmen den mest populære, da den i de fleste situationer kører hurtigere end andre. Dens tidskompleksitet er O(N*logN).
Flet sortering
Denne slags er også populær. Det er en af mange algoritmer, der bygger på princippet om "del og hersk". Sådanne algoritmer opdeler først problemet i håndterbare dele (quicksort er endnu et eksempel på en sådan algoritme). Så hvad er kernen i denne algoritme?
Dele:
Arrayet er opdelt i to dele af omtrent samme størrelse. Hver af disse to dele er delt i to mere, og så videre, indtil de mindst mulige udelelige dele er tilbage. Vi har de mindste udelelige dele, når hvert array har ét element, altså et array der allerede er sorteret.
Erobre:
Det er her, vi begynder processen, der gav algoritmen dens navn: fletning. For at gøre dette tager vi de to resulterende sorterede arrays og slår dem sammen til en. I dette tilfælde skrives det mindste af de første elementer i de to arrays ind i det resulterende array. Denne operation gentages, indtil alle elementerne i disse to arrays er blevet kopieret over. Det vil sige, at hvis vi har to minimale arrays {6} og {4}, sammenligner vi deres værdier og genererer dette flettede resultat: {4,6}. Hvis vi har sorteret arrays {4,6} og {2,8}, sammenligner vi først værdierne 4 og 2, og derefter skriver vi 2 i det resulterende array. Derefter vil 4 og 8 blive sammenlignet, og vi skriver 4. Til sidst vil 6 og 8 blive sammenlignet. I overensstemmelse hermed skriver vi 6, og først derefter skriver vi 8. Som et resultat får vi følgende flettede array: {2,4,6,8}. Hvordan vil dette se ud i Java-kode? For at køre denne algoritme vil det være praktisk for os at bruge rekursion:
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;
}
}
Som ved hurtig sortering flytter vi den rekursive metode til en mellemmetode, så brugeren kun behøver at levere det array, der skal sorteres, og ikke behøver at bekymre sig om at levere yderligere standardargumenter. Denne algoritme har ligheder med quicksort, og ikke overraskende er dens udførelseshastighed den samme: O(N*logN).
2. Grådige algoritmer
En grådig algoritme er en tilgang, hvor der træffes lokalt optimale beslutninger på hvert trin, med den antagelse, at den endelige løsning også vil være optimal. Den "optimale" løsning vil være den, der giver den mest åbenlyse og umiddelbare fordel på et bestemt trin/stadie. For at udforske denne algoritme, lad os tage et ret almindeligt problem - rygsækproblemet. Lad som om du er en tyv et øjeblik. Du er brudt ind i en butik om natten med en rygsæk (rygsæk). Foran dig er der adskillige varer, som du kunne stjæle. Men samtidig har din rygsæk begrænset kapacitet. Den kan ikke bære mere end 30 vægtenheder. Du ønsker også at bære det mest værdifulde sæt varer væk, der passer ind i rygsækken. Hvordan bestemmer du, hvad du skal putte i din taske? Så,
Vælg den dyreste vare, der ikke er taget endnu.
Hvis den passer i rygsækken, så læg den i. Hvis ikke, så lad den stå.
Har vi allerede stjålet alt? Hvis ikke, vender vi tilbage til trin 1. Hvis ja, så tager vi vores hurtige flugt fra butikken, da vi har opnået det, vi kom for at gøre.
Lad os se på dette, men i Java. Sådan vil Item-klassen se ud:
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;
}
}
Der er ikke noget særligt her: tre felter (navn, vægt, værdi), der definerer varens egenskaber. Som du kan se, er den sammenlignelige grænseflade også implementeret for at give os mulighed for at sortere vores varer efter pris. Dernæst vil vi se på taskeklassen, som repræsenterer vores rygsæk:
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 er vores rygsæks kapacitet, som indstilles, når vi skaber et objekt;
genstande repræsenterer genstandene i vores rygsæk;
currentWeight , currentValue — disse felter gemmer den aktuelle vægt og værdi af alle varer i rygsækken, som vi øger, når vi tilføjer en ny vare i addItem-metoden.
Uanset hvad, lad os nu gå til klassen, hvor alle handlinger finder sted:
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());
}
}
Først opretter vi en liste over elementer og sorterer den. Vi skaber et poseobjekt med en kapacitet på 30 enheder. Dernæst videregiver vi genstandene og poseobjektet til fillBackpack-metoden, som fylder rygsækken i henhold til vores grådige algoritme:
Det er ret simpelt: Vi begynder at gennemgå en liste over varer sorteret efter pris og lægge dem i posen, hvis dens kapacitet tillader det. Hvis der ikke er plads nok, springes emnet over, og vi fortsætter med at krydse resten af emnerne, indtil vi når slutningen af listen. Når vi kører main, her er konsoludgangen, vi får:
Rygsækkens vægt er 29. Den samlede værdi af genstande i rygsækken er 3700
Dette er et eksempel på en grådig algoritme: Ved hvert trin vælges en lokalt optimal løsning, og i sidste ende får du en globalt optimal løsning. I vores tilfælde er den bedste mulighed den dyreste vare. Men er dette den bedste løsning? Tror du ikke, det er muligt at forbedre vores løsning lidt for at fylde vores rygsæk med varer, der har endnu større samlet værdi? Lad os tage et kig på, hvordan dette kan gøres.
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());
}
}
}
Her beregner vi først værdi-til-vægt-forholdet for hver vare. Dette fortæller os værdien af hver enhed af en given vare. Og så bruger vi disse forhold til at sortere vores varer og tilføje dem til vores taske. Lad os køre følgende:
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());
Vi får denne konsoludgang:
Vægten af rygsækken er 29. Den samlede pris for varer i rygsækken er 4150,-
Lidt bedre, ikke? Den grådige algoritme træffer et lokalt optimalt valg ved hvert trin i håb om, at den endelige løsning også bliver optimal. Denne antagelse er ikke altid gyldig, men for mange opgaver giver grådige algoritmer en optimal endelig løsning. Tidskompleksiteten af denne algoritme er O(N). Ret godt, ikke?
Og da du er på denne hjemmeside, vil jeg være så dristig at antage, at du skriver i Java. Derfor foreslår jeg i dag, at du gør dig bekendt med nogle grundlæggende algoritmer og med specifikke eksempler på, hvordan du implementerer dem i Java. Med "nogle" mener jeg:
GO TO FULL VERSION