Sortering är en av de grundläggande operationerna som vi utför på objekt. Redan i barndomen lär man barn att sortera när de utvecklar sina tankeförmåga. Datorer och mjukvara är inget undantag. Det finns ett stort utbud av sorteringsalgoritmer i Java . Jag föreslår att du kollar in vad de är och hur de fungerar. Tänk om du blir tillfrågad om en av dem på en intervju någon dag?
Introduktion
Sorteringselement är en av kategorierna av algoritmer som en utvecklare måste känna till. Om datavetenskap en gång inte togs på allvar när jag gick i skolan måste dagens elever kunna implementera och förstå sorteringsalgoritmer. Grundläggande algoritmer, de enklaste, implementeras med en for- loop. Naturligtvis, för att sortera en samling av element, till exempel en array, måste du på något sätt gå igenom samlingen. Till exempel:
int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
Vad kan man säga om detta kodsegment? Vi har en slinga där vi ändrar indexet ( int i) från 0 till det sista elementet i arrayen. Faktum är att vi helt enkelt tar varje element i arrayen och skriver ut dess innehåll. Ju fler element i arrayen, desto längre tid tar det att slutföra koden. Det vill säga, om när antalet element, när n = 10programmet kommer att ta dubbelt så lång tid att köra än när n = 5. Om vårt program har en enda loop, växer exekveringstiden linjärt: ju fler element det finns, desto längre blir exekveringstiden. Det visar sig att algoritmen ovan fungerar i linjär tid (en linjär funktion av n). I sådana fall säger vi att algoritmens komplexitet är "O(n)". Denna notation kallas också "big O" eller "asymptotiskt beteende". Men du kan bara komma ihåg "
Den enklaste sorteringsalgoritmen (bubbelsortering)
Anta att vi har en array och vi kan iterera genom den. Bra. Låt oss nu försöka sortera det i stigande ordning. Vad betyder det här? Det betyder att givet två element (till exempel , a = 6) b = 5, måste vi ordna om aoch bif aär större än b(if a > b). Vad betyder detta när vi använder ett index för att arbeta med en samling (som är fallet med en array)? Det betyder att om elementet med index a är större än elementet med index ( b) array[a] > array[b], måste elementen bytas. Det finns olika sätt att byta plats på. Men vi kommer att använda en teknik som är enkel, begriplig och lätt att komma ihåg:
private void swap(int[] array, int ind1, int ind2) {
int tmp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = tmp;
}
Nu kan vi skriva följande:
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));
Som du kan se byttes elementen verkligen ut. Vi började med index 1, för om arrayen bara har ett element array[i] < array[i-1]är uttrycket ogiltigt för index 0. Att göra detta skyddar oss också från fall där arrayen inte har några element eller bara ett element, och det gör att koden ser bättre ut. Men den resulterande arrayen är fortfarande inte sorterad, eftersom ett pass inte räcker för att utföra sorteringen. Vi måste lägga till en annan slinga där vi kommer att utföra pass igen och igen tills vi får en sorterad array:
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));
Så vi avslutade vår första sorteringsalgoritm. Vi upprepar den yttre slingan ( while) tills vi bestämmer oss för att inga fler iterationer behövs. Som standard, före varje ny iteration, antar vi att vår array är sorterad och att vi inte behöver loopa längre. Följaktligen rör vi oss sekventiellt genom elementen och kontrollerar detta antagande. Men om elementen inte är i ordning, så byter vi element och förstår att vi nu inte har någon garanti för att elementen är i rätt ordning. Det betyder att vi måste utföra en till iteration. Anta till exempel att vi har [3, 5, 2]. 5är mer än 3- allt är bra. Men 2är mindre än 5. Kräver dock [3, 2, 5]ytterligare ett pass, eftersom3 > 2och de måste bytas. Eftersom vi använder en loop i en loop, ökar komplexiteten i vår algoritm. Givet nelement blir det n * n, det vill säga O(n^2). Detta kallas kvadratisk komplexitet. I allmänhet kan vi inte veta exakt hur många iterationer som kommer att behövas. Uttrycket för en algoritms komplexitet visar hur komplexiteten ökar i värsta fall. Det vill säga, det indikerar hur mycket exekveringstiden kommer att öka när antalet element nändras. Bubblesortering är en av de enklaste och mest ineffektiva sorteringsalgoritmerna. Det kallas också ibland för "dum sort". Material om detta ämne:
En annan sorteringsalgoritm är urvalssortering. Den har också kvadratisk komplexitet, men mer om det senare. Så idén är enkel. Vid varje pass väljer vi det minsta elementet och flyttar det till början. Dessutom börjar varje pass ett steg till höger. Med andra ord, det första passet börjar från det nollte elementet, det andra passet från det första, etc. Det kommer att se ut så här:
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));
Denna sort är instabil, eftersom identiska element (i termer av vilken egenskap vi än använder för att sortera elementen) kan ändra sina relativa positioner. Det finns ett bra exempel i Wikipedia-artikeln om urvalssortering . Material om detta ämne:
Insättningssort har också kvadratisk komplexitet, eftersom vi återigen har en loop i en loop. Vad är det som skiljer insättningssortering? Denna sorteringsalgoritm är "stabil". Detta innebär att identiska element inte kommer att ändra sin relativa ordning. Återigen menar vi identiska när det gäller de egenskaper vi sorterar efter.
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));
Shuttle sortera
Det finns en annan enkel sorteringsalgoritm: skyttelsortering. Detta är också känt som en dubbelriktad bubbelsortering eller cocktailshakersorten. Dessa alternativa namn säger oss att skyttelsorten inte handlar om rymdfärjan. Det handlar om något som rör sig fram och tillbaka. Nu kan du tänka på det när du tänker på den här algoritmen. Vad är kärnan i algoritmen? Kärnan i algoritmen är att vi itererar från vänster till höger, byter element och kontrollerar om något av elementen som finns kvar i den andra riktningen behöver bytas.
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));
En annan enkel sorteringsalgoritm är skalsortering. Kontentan av det liknar bubbelsortering, men i varje iteration har vi ett annat gap mellan de jämförda elementen. Den skärs på mitten med varje iteration. Här är en implementering:
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));
Utöver dessa enkla sorteringsalgoritmer finns det även mer komplicerade sorteringsalgoritmer. Till exempel, slå samman sortering. Det finns två saker att notera. Först kommer rekursion till vår räddning här. För det andra är algoritmens komplexitet inte längre kvadratisk, som vi är vana vid. Denna algoritms komplexitet är logaritmisk. Detta är skrivet som O(n log n). Så låt oss implementera det. Först kommer vi att skriva ett rekursivt anrop till sorteringsmetoden:
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);
}
}
Låt oss nu lägga till huvudåtgärden i vår implementering. Här är vår supermetod:
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);
}
Vi kan köra vårt exempel genom att ringamergeSort(array, 0, array.length-1). Som du kan se, går processen ner till att acceptera en inmatningsmatris tillsammans med indikationer på början och slutet av avsnittet som behöver sorteras. När sorteringen börjar är dessa början och slutet av arrayen. Sedan beräknar vi avgränsaren, som är indexet där vi kommer att dela upp arrayen. Om arrayen kan delas upp i 2 delar, då kallar vi sorteringsmetoden rekursivt för de två halvorna av arrayen. Vi förbereder en extra buffert där vi infogar den sorterade sektionen. Ställ sedan in indexet i början av avsnittet som ska sorteras och börja gå igenom varje element i den tomma bufferten, fyll det med de minsta elementen. Om elementet som indexet pekar på är mindre än elementet som avgränsaren pekar på, lägger vi elementet i bufferten och flyttar indexet. Annat, vi placerar elementet som avgränsaren pekar på i bufferten och flyttar avgränsaren. Så snart avgränsaren går utanför gränserna för den sektion som sorteras eller vi fyller hela arrayen, anses det angivna intervallet vara sorterat.Material om detta ämne:
En annan intressant sorteringsalgoritm är att räkna sortering. Den algoritmiska komplexiteten här är O(n+k), där när antalet element och kär det maximala värdet för ett element. Den här algoritmen har en brist: vi måste känna till minimi- och maximivärdena i arrayen. Här är ett exempel på räkningssorten:
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;
}
Du kan förstå att det är väldigt obekvämt när vi i förväg behöver veta minimi- och maxvärdena. Och vi har en annan algoritm här: radix sort. Jag kommer bara att presentera algoritmen här visuellt. Se tilläggsmaterialet för implementeringen: Material:
Nåväl, det är dags för efterrätt — snabb sortering, en av de mest kända sorteringsalgoritmerna. Den har logaritmisk komplexitet: O(n log n). Denna sorteringsalgoritm utvecklades av Tony Hoare. Intressant nog uppfann han det medan han bodde i Sovjetunionen, där han studerade maskinöversättning vid Moskvas universitet och utvecklade en rysk-engelsk parlör. Dessutom använder Java en mer komplex version av denna algoritm i Arrays.sort. Vad sägs om Collections.sort? Varför inte ta en titt på hur saker sorteras "under huven"? Här är koden:
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);
}
}
Det här är väldigt läskigt, så låt oss gräva i det. För inmatningsmatris ( int[]källa) skapar vi två markörer: vänster ( L) och höger ( ) R. Under det första metodanropet motsvarar de början och slutet av arrayen. Sedan identifierar vi pivotelementet, som det passande namnet pivot. Efter detta är vår uppgift att flytta värden mindre än pivottill vänster om pivot, och större - till höger. För att göra detta flyttar vi först markören Ltills vi hittar ett värde som är större än pivot. Om inget mindre värde hittas, då
L blir lika med
pivot. Sedan flyttar vi
Rmarkören tills vi hittar ett värde som är mindre än
pivot. Om inget större värde hittas
Rblir det lika med
pivot. Därefter, om
Lmarkören är före
Rmarkören eller sammanfaller med den, försöker vi byta elementen om elementet
Lär mindre än
Relementet. Sedan växlar vi
Låt höger med 1, och vi växlar
Råt vänster med 1. När
Lmarkören rör sig bortom
Rmarkören betyder det att bytet är klart: mindre värden är till vänster om ,
pivotstörre värden är till höger om
pivot. Efter detta anropar vi samma sorteringsmetod rekursivt på subarrayerna — från början av avsnittet som ska sorteras till höger markör och från vänster markör till slutet av avsnittet som ska sorteras. Varför från början till höger markör? För i slutet av en iteration visar det sig att den högra markören rör sig tillräckligt mycket för att bli gränsen för den vänstra delen. Denna algoritm är mer komplex än enkel sortering, så det är bäst att skissa den. Ta ett vitt papper och skriv: 4 2 6 7 3. Skriv sedan
pivoti mitten, dvs under nummer 6. Ringa in det. Under 4, skriv
L, och under 3, skriv
R. 4 mindre än 6, 2 mindre än 6. Det slutar med att vi flyttar
Ltill
pivotpositionen, för
Lkan inte gå förbi
pivot, enligt villkoret. Skriv igen 4 2 6 7 3. Ringa in 6 (
pivot) och lägg
Lunder. Flytta nu markören
R. 3 är mindre än 6, så sätt markören
Rpå 3. Eftersom 3 är mindre än 6 (
pivot), utför vi en
swap. Skriv resultatet: 4 2 3 7 6. Ring in 6, eftersom det fortfarande är
pivot. Markören
Lär på 3.
RMarkören är på 6. Kom ihåg att vi flyttar markörerna tills
Lden går bortom
R. Flytta
Ltill nästa nummer. Här skulle jag vilja utforska två möjligheter: 1) fallet där det näst sista talet är 7 och 2) fallet där det är 1, inte 7.
Om det näst sista talet är 1: Flytta
Lmarkören till 1, eftersom vi kan flytta
Lså länge som
Lmarkören pekar på ett nummer som är mindre än
pivot. Men vi kan inte flytta
Rfrån 6, eftersom vi bara kan flytta R om
Rmarkören pekar på ett tal som är större än
pivot. Vi utför inte en
swap, eftersom 1 är mindre än 6. Skriv den aktuella situationen: 4 2 3 1 6. Cirkel 6 (
pivot).
Lväxlar förbi
pivotoch slutar röra sig.
Rrör sig inte. Vi gör inget byte. Skift
Loch
Rmed en position. Skriv
Rmarkören under 1.
LMarkören är utanför gränserna. Eftersom
Ldet är utanför ramarna gör vi ingenting. Men vi skriver 4 2 3 1 igen, eftersom detta är vår vänstra sida, som är mindre än
pivot(6). Välj den nya
pivotoch starta allt igen :)
Om näst sista siffran är 7:Flytta
Lmarkören till 7. Vi kan inte flytta den högra markören, eftersom den redan pekar mot pivoten. 7 är större än
pivot, så vi utför en
swap. Skriv resultatet: 4 2 3 6 7. Ring in 6, eftersom det är
pivot. Markören
Lflyttas nu till 7, och
Rmarkören flyttas till 3. Det är inte meningsfullt att sortera delen från
Ltill slutet, eftersom det bara finns ett element. Däremot skickar vi delen från 4 till markören
Rför sortering. Vi väljer a
pivotoch börjar om från början :) Vid första anblicken kan det tyckas att om man lägger till många värden lika med
pivot, då kommer du att bryta algoritmen. Men detta är inte fallet. Du kan komma på knepiga kombinationer och på papper övertyga dig själv om att allt är korrekt och förundras över att så enkla åtgärder implementerar en så tillförlitlig sorteringsmekanism. Den enda nackdelen är att denna sorteringsalgoritm inte är stabil. Eftersom ett byte kan ändra den relativa ordningen för identiska element om ett av dem har påträffats tidigare
pivotinnan det andra elementet byts till delen före
pivot.
Poängen
Ovan tittade vi på en "gentleman's" uppsättning sorteringsalgoritmer implementerade i Java. Algoritmer är generellt sett användbara, både ur ett tillämpat perspektiv och när det gäller att lära sig tänka. Vissa är enklare, andra är mer komplicerade. Smarta människor disputerade för vissa. För andra skrev de supertjocka böcker. Jag hoppas att tilläggsmaterialet kommer att hjälpa dig att lära dig ännu mer, eftersom den här artikeln bara är en översikt som redan har visat sig vara tung. Och dess syfte är att ge en liten introduktion. Du kan också hitta en introduktion till algoritmer om du läser
"Grokking Algorithms" . Jag gillar också spellistan från Jack Brown:
AQA Decision 1 1.01 Tracing an Algorithm . För skojs skull kan du se algoritmvisualiseringar vid
sortering.visualgo.net .
GO TO FULL VERSION