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?
L blir lika med
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 = 10
programmet 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 a
och b
if 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 > 2
och de måste bytas. Eftersom vi använder en loop i en loop, ökar komplexiteten i vår algoritm. Givet n
element 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:
Urvalssortering
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
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));
Material om detta ämne:
Skalsort
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));
Material om detta ämne:
Slå samman sortering
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 somO(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:
Räkna sort och radix sort
En annan intressant sorteringsalgoritm är att räkna sortering. Den algoritmiska komplexiteten här ärO(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:
Snabb sortering
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 pivot
till vänster om pivot
, och större - till höger. För att göra detta flyttar vi först markören L
tills vi hittar ett värde som är större än pivot
. Om inget mindre värde hittas, dåpivot
. Sedan flyttar vi
R
markören tills vi hittar ett värde som är mindre än
pivot
. Om inget större värde hittas
R
blir det lika med
pivot
. Därefter, om
L
markören är före
R
markören eller sammanfaller med den, försöker vi byta elementen om elementet
L
är mindre än
R
elementet. Sedan växlar vi
L
åt höger med 1, och vi växlar
R
åt vänster med 1. När
L
markören rör sig bortom
R
markören betyder det att bytet är klart: mindre värden är till vänster om ,
pivot
stö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
pivot
i 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
L
till
pivot
positionen, för
L
kan inte gå förbi
pivot
, enligt villkoret. Skriv igen 4 2 6 7 3. Ringa in 6 (
pivot
) och lägg
L
under. Flytta nu markören
R
. 3 är mindre än 6, så sätt markören
R
på 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.
R
Markören är på 6. Kom ihåg att vi flyttar markörerna tills
L
den går bortom
R
. Flytta
L
till 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
L
markören till 1, eftersom vi kan flytta
L
så länge som
L
markören pekar på ett nummer som är mindre än
pivot
. Men vi kan inte flytta
R
från 6, eftersom vi bara kan flytta R om
R
markö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
).
L
växlar förbi
pivot
och slutar röra sig.
R
rör sig inte. Vi gör inget byte. Skift
L
och
R
med en position. Skriv
R
markören under 1.
L
Markören är utanför gränserna. Eftersom
L
det ä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
pivot
och starta allt igen :)
Om näst sista siffran är 7:Flytta
L
markö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
L
flyttas nu till 7, och
R
markören flyttas till 3. Det är inte meningsfullt att sortera delen från
L
till slutet, eftersom det bara finns ett element. Däremot skickar vi delen från 4 till markören
R
för sortering. Vi väljer a
pivot
och 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
pivot
innan det andra elementet byts till delen före
pivot
.