Sortering er en av de grunnleggende operasjonene vi utfører på objekter. Selv i barndommen læres barn å sortere etter hvert som de utvikler tankeferdighetene sine. Datamaskiner og programvare er intet unntak. Det finnes et stort utvalg av sorteringsalgoritmer i Java . Jeg foreslår at du sjekker ut hva de er og hvordan de fungerer. Hva om du blir spurt om en av dem på et intervju en dag?
Introduksjon
Sorteringselementer er en av kategoriene av algoritmer som en utvikler må kjenne til. Hvis datavitenskap en gang ikke ble tatt på alvor da jeg gikk på skolen, må dagens elever kunne implementere og forstå sorteringsalgoritmer. Grunnleggende algoritmer, de enkleste, implementeres ved hjelp av en for- løkke. Naturligvis, for å sortere en samling av elementer, for eksempel en matrise, må du på en eller annen måte gå gjennom samlingen. For eksempel:
int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
Hva kan sies om dette kodesegmentet? Vi har en løkke der vi endrer indeksen ( int i) fra 0 til det siste elementet i matrisen. Faktisk tar vi ganske enkelt hvert element i matrisen og skriver ut innholdet. Jo flere elementer i matrisen, desto lengre tid vil koden ta å fullføre. Det vil si, hvis ner antall elementer, når n = 10programmet vil ta dobbelt så lang tid å kjøre enn når n = 5. Hvis programmet vårt har en enkelt sløyfe, vokser utførelsestiden lineært: jo flere elementer det er, jo lengre blir utførelsestiden. Det viser seg at algoritmen ovenfor fungerer i lineær tid (en lineær funksjon av n). I slike tilfeller sier vi at algoritmens kompleksitet er "O(n)". Denne notasjonen kalles også "big O" eller "asymptotisk oppførsel". Men du kan bare huske"
Den enkleste sorteringsalgoritmen (boblesortering)
Anta at vi har en matrise og vi kan iterere gjennom den. Flott. La oss nå prøve å sortere det i stigende rekkefølge. Hva betyr dette? Det betyr at gitt to elementer (for eksempel , a = 6) b = 5, må vi omorganisere aog bhvis aer større enn b(hvis a > b). Hva betyr dette når vi bruker en indeks for å jobbe med en samling (som tilfellet er med en matrise)? Det betyr at hvis elementet med indeks a er større enn elementet med indeks b( array[a] > array[b]), så må elementene byttes. Det er forskjellige måter å bytte plass på. Men vi bruker en teknikk som er enkel, forståelig og lett å huske:
private void swap(int[] array, int ind1, int ind2) {
int tmp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = tmp;
}
Nå kan vi skrive følgende:
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, ble elementene virkelig byttet. Vi startet med indeks 1, fordi hvis matrisen bare har ett element, array[i] < array[i-1]er uttrykket ugyldig for indeks 0. Å gjøre dette beskytter oss også mot tilfeller der matrisen ikke har noen elementer eller bare ett element, og det får koden til å se bedre ut. Men den resulterende matrisen er fortsatt ikke sortert, fordi ett pass ikke er nok til å utføre sorteringen. Vi må legge til en annen løkke der vi vil utføre pasninger igjen og igjen til vi får en sortert matrise:
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 fullførte vår første sorteringsalgoritme. Vi gjentar den ytre løkken ( while) til vi bestemmer oss for at det ikke er behov for flere iterasjoner. Som standard, før hver ny iterasjon, antar vi at matrisen vår er sortert og at vi ikke trenger å gå i loop lenger. Følgelig beveger vi oss sekvensielt gjennom elementene og sjekker denne antagelsen. Men hvis elementene ikke er i orden, så bytter vi elementer og forstår at vi nå ikke har noen garanti for at elementene er i riktig rekkefølge. Dette betyr at vi må utføre en ny iterasjon. Anta for eksempel at vi har [3, 5, 2]. 5er mer enn 3- alt er bra. Men 2er mindre enn 5. Men [3, 2, 5]krever en annen pass, siden3 > 2og de må byttes. Fordi vi bruker en løkke i en løkke, øker kompleksiteten til algoritmen vår. Gitt nelementer blir det n * n, altså O(n^2). Dette kalles kvadratisk kompleksitet. Generelt kan vi ikke vite nøyaktig hvor mange iterasjoner som vil være nødvendig. Uttrykket for kompleksitet til en algoritme viser hvordan kompleksiteten øker i verste fall. Det vil si at den indikerer hvor mye utførelsestiden vil øke ettersom antall elementer nendres. Boblesortering er en av de enkleste og mest ineffektive sorteringsalgoritmene. Det kalles også noen ganger "dum sort". Materiale om dette emnet:
En annen sorteringsalgoritme er utvalgssortering. Den har også kvadratisk kompleksitet, men mer om det senere. Så ideen er enkel. På hvert pass velger vi det minste elementet og flytter det til begynnelsen. I tillegg starter hvert pass ett trinn til høyre. Med andre ord, den første passeringen starter fra det nullte elementet, den andre passeringen fra den første osv. Det vil se slik ut:
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));
Denne typen er ustabil, fordi identiske elementer (med hensyn til hvilken egenskap vi bruker for å sortere elementene) kan endre deres relative posisjoner. Det er et godt eksempel i Wikipedia-artikkelen om utvalgssortering . Materiale om dette emnet:
Innsettingssortering har også kvadratisk kompleksitet, siden vi igjen har en løkke i en løkke. Hva gjør innsettingssortering annerledes? Denne sorteringsalgoritmen er "stabil". Dette betyr at identiske elementer ikke vil endre sin relative rekkefølge. Igjen mener vi identiske når det gjelder egenskapene vi sorterer etter.
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));
Transport sortering
Det er en annen enkel sorteringsalgoritme: skyttelsortering. Dette er også kjent som en toveis boblesortering eller cocktailshaker-sortering. Disse alternative navnene forteller oss at skyttelsorten ikke handler om romfergen. Det handler om noe som beveger seg frem og tilbake. Nå kan du tenke på det når du tenker på denne algoritmen. Hva er essensen av algoritmen? Essensen av algoritmen er at vi itererer fra venstre til høyre, bytter elementer og sjekker om noen av elementene som er igjen i den andre retningen må byttes.
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 annen enkel sorteringsalgoritme er skallsortering. Hoveddelen av det ligner på boblesortering, men i hver iterasjon har vi et annet gap mellom de sammenlignede elementene. Den kuttes i to for hver iterasjon. Her er 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));
I tillegg til disse enkle sorteringsalgoritmene finnes det også mer kompliserte sorteringsalgoritmer. For eksempel, slå sammen sortering. Det er to ting å merke seg. For det første kommer rekursjon oss til unnsetning her. For det andre er algoritmens kompleksitet ikke lenger kvadratisk, slik vi er vant til. Denne algoritmens kompleksitet er logaritmisk. Dette er skrevet som O(n log n). Så la oss implementere det. Først vil vi skrive et rekursivt kall til 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);
}
}
La oss nå legge til hovedhandlingen i implementeringen vår. Her er supermetoden vår:
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 kjøre vårt eksempel ved å ringemergeSort(array, 0, array.length-1). Som du kan se, koker prosessen ned til å akseptere en input-array sammen med indikasjoner på begynnelsen og slutten av delen som må sorteres. Når sorteringen begynner, er disse begynnelsen og slutten av matrisen. Deretter beregner vi skilletegnet, som er indeksen der vi skal dele matrisen. Hvis matrisen kan deles i 2 deler, kaller vi sorteringsmetoden rekursivt for de to halvdelene av matrisen. Vi forbereder en hjelpebuffer der vi setter inn den sorterte delen. Deretter setter du indeksen i begynnelsen av delen som skal sorteres, og begynner å gå gjennom hvert element i den tomme bufferen, og fyll den med de minste elementene. Hvis elementet som indeksen peker på er mindre enn elementet peker på av skilletegnet, legger vi elementet i bufferen og forskyver indeksen. Ellers, vi plasserer elementet som skillet peker på i bufferen og flytter skilletegnet. Så snart skilletegnet går utover grensene til seksjonen som sorteres eller vi fyller hele matrisen, anses det angitte området som sortert.Materiale om dette emnet:
En annen interessant sorteringsalgoritme er tellesortering. Den algoritmiske kompleksiteten her er O(n+k), hvor ner antall elementer og ker maksimumsverdien til et element. Denne algoritmen har en mangel: vi trenger å vite minimums- og maksimumsverdiene i matrisen. Her er et eksempel på telleslag:
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 forstå at det er veldig upraktisk når vi på forhånd trenger å vite minimums- og maksimumsverdiene. Og vi har en annen algoritme her: radix sort. Jeg vil kun presentere algoritmen her visuelt. Se tilleggsmateriell for implementeringen: Materialer:
Vel, det er tid for dessert - rask sortering, en av de mest kjente sorteringsalgoritmene. Den har logaritmisk kompleksitet: O(n log n). Denne sorteringsalgoritmen ble utviklet av Tony Hoare. Interessant nok oppfant han det mens han bodde i Sovjetunionen, hvor han studerte maskinoversettelse ved Moskva-universitetet og utviklet en russisk-engelsk parlør. Dessuten bruker Java en mer kompleks versjon av denne algoritmen i Arrays.sort. Hva med Collections.sort? Hvorfor ikke ta en titt på hvordan ting er sortert "under panseret"? Her er 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);
}
}
Alt dette er veldig skummelt, så la oss grave i det. For input array ( int[]kilde) lager vi to markører: venstre ( L) og høyre ( R). Under det første metodekallet tilsvarer de begynnelsen og slutten av matrisen. Deretter identifiserer vi pivotelementet, som er passende kalt pivot. Etter dette er oppgaven vår å flytte verdier mindre enn pivottil venstre for pivot, og større - til høyre. For å gjøre dette, flytter vi først markøren Ltil vi finner en verdi større enn pivot. Hvis ingen mindre verdi er funnet, da
L blir lik
pivot. Så flytter vi
Rmarkøren til vi finner en verdi mindre enn
pivot. Hvis ingen større verdi er funnet,
Rblir lik
pivot. Deretter, hvis
Lmarkøren er før
Rmarkøren eller sammenfaller med den, prøver vi å bytte ut elementene hvis elementet
Ler mindre enn
Relementet. Deretter skifter vi
Ltil høyre med 1, og vi skifter
Rtil venstre med 1. Når
Lmarkøren beveger seg forbi
Rmarkøren, betyr det at byttet er fullført: mindre verdier er til venstre for
pivot, større verdier er til høyre for
pivot. Etter dette kaller vi den samme sorteringsmetoden rekursivt på undermatrisene - fra begynnelsen av delen som skal sorteres til høyre markør, og fra venstre markør til slutten av delen som skal sorteres. Hvorfor fra begynnelsen til høyre markør? For på slutten av en iterasjon viser det seg at høyre markør beveger seg nok til å bli grensen til venstre del. Denne algoritmen er mer kompleks enn enkel sortering, så det er best å skissere den. Ta et hvitt ark og skriv: 4 2 6 7 3. Skriv så
pivotpå midten, altså under nummer 6. Sett ring rundt. Under 4, skriv
L, og under 3, skriv
R. 4 mindre enn 6, 2 mindre enn 6. Vi ender opp med å flytte
Ltil
pivotposisjonen, fordi
Lkan ikke gå forbi
pivot, i henhold til tilstanden. Skriv på nytt 4 2 6 7 3. Sett ring rundt 6 (
pivot) og legg
Lunder. Flytt nå
Rmarkøren. 3 er mindre enn 6, så sett markøren
Rpå 3. Siden 3 er mindre enn 6 (
pivot), utfører vi en
swap. Skriv resultatet: 4 2 3 7 6. Sirkel 6, fordi det fortsatt er
pivot. Markøren
Ler på 3.
RMarkøren står på 6. Husk at vi flytter markørene til
Lflytter forbi
R. Gå
Ltil neste nummer. Her vil jeg utforske to muligheter: 1) tilfellet der det nest siste tallet er 7 og 2) tilfellet hvor det er 1, ikke 7.
Hvis det nest siste tallet er 1: Flytt
Lmarkøren til 1, fordi vi kan flytte
Lså lenge
Lmarkøren peker på et tall som er mindre enn
pivot. Men vi kan ikke flytte
Rfra 6, fordi vi bare kan flytte R hvis markøren
Rpeker på et tall som er større enn
pivot. Vi utfører ikke en
swap, fordi 1 er mindre enn 6. Skriv den aktuelle situasjonen: 4 2 3 1 6. Sirkel 6 (
pivot).
Lskifter forbi
pivotog slutter å bevege seg.
Rbeveger seg ikke. Vi bytter ikke. Skift
Log
Rmed én posisjon. Skriv
Rmarkøren under 1.
LMarkøren er utenfor feltene. Fordi
Ler utenfor grensene, gjør vi ingenting. Men vi skriver 4 2 3 1 igjen, fordi dette er vår venstre side, som er mindre enn
pivot(6). Velg den nye
pivotog start alt på nytt :)
Hvis det nest siste tallet er 7:Flytt
Lmarkøren til 7. Vi kan ikke flytte den høyre markøren, fordi den allerede peker mot pivoten. 7 er større enn
pivot, så vi utfører en
swap. Skriv resultatet: 4 2 3 6 7. Sirkel 6, fordi det er
pivot. Markøren
Ler nå forskjøvet til 7, og
Rmarkøren flyttes til 3. Det er ikke fornuftig å sortere delen fra
Ltil slutten, fordi det bare er 1 element. Vi sender imidlertid delen fra 4 til markøren
Rfor sortering. Vi velger a
pivotog begynner på nytt igjen :) Ved første øyekast kan det virke som om man legger til mange verdier lik
pivot, så bryter du algoritmen. Men dette er ikke tilfelle. Du kan tenke på vanskelige kombinasjoner og på papiret overbevise deg selv om at alt er riktig og forundre deg over at slike enkle handlinger implementerer en så pålitelig sorteringsmekanisme. Den eneste ulempen er at denne sorteringsalgoritmen ikke er stabil. Fordi en swap kan endre den relative rekkefølgen til identiske elementer hvis ett av dem er påtruffet før
pivotfør det andre elementet byttes inn i delen før
pivot.
Bunnlinjen
Ovenfor så vi på et "gentlemans" sett med sorteringsalgoritmer implementert i Java. Algoritmer er generelt nyttige, både fra et anvendt perspektiv og når det gjelder å lære å tenke. Noen er enklere, noen er mer kompliserte. Smarte mennesker disputerte for noen. For andre skrev de supertykke bøker. Jeg håper tilleggsmateriellet vil hjelpe deg med å lære enda mer, siden denne artikkelen bare er en oversikt som allerede har vist seg å være tungtveiende. Og formålet er å gi en liten introduksjon. Du kan også finne en introduksjon til algoritmer hvis du leser
"Grokking Algorithms ". Jeg liker også spillelisten fra Jack Brown:
AQA Decision 1 1.01 Tracing an Algorithm . For moro skyld kan du se algoritmevisualiseringer ved
sortering.visualgo.net .
GO TO FULL VERSION