Sortering er en af de grundlæggende operationer, som vi udfører på objekter. Selv i barndommen bliver børn lært at sortere, efterhånden som de udvikler deres tankefærdigheder. Computere og software er ingen undtagelse. Der er et stort udvalg af sorteringsalgoritmer i Java . Jeg foreslår, at du tjekker ud, hvad de er, og hvordan de fungerer. Hvad hvis du bliver spurgt om en af dem til et interview en dag?
Introduktion
Sorteringselementer er en af de kategorier af algoritmer, som en udvikler skal kende. Hvis datalogi engang ikke blev taget seriøst, da jeg gik i skole, skal nutidens elever kunne implementere og forstå sorteringsalgoritmer. Grundlæggende algoritmer, de enkleste, implementeres ved hjælp af en for- løkke. For at sortere en samling af elementer, såsom et array, skal du naturligvis på en eller anden måde gennemgå 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]);
}
Hvad kan man sige om dette kodesegment? Vi har en loop, hvor vi ændrer indekset ( int i) fra 0 til det sidste element i arrayet. Faktisk tager vi simpelthen hvert element i arrayet og udskriver dets indhold. Jo flere elementer i arrayet, jo længere tid tager koden at afslutte. Det vil sige, hvis ner antallet af elementer, når n = 10programmet vil tage dobbelt så lang tid at køre, end når n = 5. Hvis vores program har en enkelt løkke, vokser eksekveringstiden lineært: Jo flere elementer der er, jo længere er eksekveringstiden. Det viser sig, at algoritmen ovenfor virker i lineær tid (en lineær funktion af n). I sådanne tilfælde siger vi, at algoritmens kompleksitet er "O(n)". Denne notation kaldes også "big O" eller "asymptotisk adfærd". Men du kan bare huske"
Den enkleste sorteringsalgoritme (boblesortering)
Antag, at vi har et array, og vi kan iterere gennem det. Store. Lad os nu prøve at sortere det i stigende rækkefølge. Hvad betyder det? Det betyder, at givet to elementer (for eksempel , a = 6) b = 5, skal vi omarrangere aog bhvis aer større end b(hvis a > b). Hvad betyder det, når vi bruger et indeks til at arbejde med en samling (som det er tilfældet med en matrix)? Det betyder, at hvis elementet med indeks a er større end elementet med indeks b( array[a] > array[b]), så skal elementerne byttes. Der er forskellige måder at skifte plads på. Men vi bruger en teknik, der er enkel, forståelig og nem at huske:
private void swap(int[] array, int ind1, int ind2) {
int tmp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = tmp;
}
Nu 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, blev elementerne virkelig byttet om. Vi startede med indeks 1, for hvis arrayet kun har ét element, array[i] < array[i-1]er udtrykket ugyldigt for index 0. At gøre dette beskytter os også mod tilfælde, hvor arrayet ikke har nogen elementer eller kun ét element, og det får koden til at se bedre ud. Men det resulterende array er stadig ikke sorteret, fordi et gennemløb ikke er nok til at udføre sorteringen. Vi bliver nødt til at tilføje endnu en løkke, hvor vi vil udføre gennemløb igen og igen, indtil vi får et sorteret 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 afsluttede vores første sorteringsalgoritme. Vi gentager den ydre løkke ( while), indtil vi beslutter, at der ikke er behov for flere iterationer. Som standard, før hver ny iteration, antager vi, at vores array er sorteret, og vi behøver ikke at loope længere. Derfor bevæger vi os sekventielt gennem elementerne og kontrollerer denne antagelse. Men hvis elementerne ikke er i orden, så bytter vi elementer og forstår, at vi nu ikke har nogen garanti for, at elementerne er i den rigtige rækkefølge. Det betyder, at vi skal udføre endnu en iteration. Antag for eksempel, at vi har [3, 5, 2]. 5er mere end 3- alt er godt. Men 2er mindre end 5. Kræver dog endnu [3, 2, 5]et pas, da3 > 2og de skal byttes. Fordi vi bruger en loop i en loop, øges kompleksiteten af vores algoritme. Givet nelementer bliver det , n * ndvs. O(n^2)Dette kaldes kvadratisk kompleksitet. Generelt kan vi ikke vide nøjagtigt, hvor mange iterationer, der er nødvendige. Udtrykket for kompleksitet af en algoritme viser, hvordan kompleksiteten i værste fald stiger. Det vil sige, at det angiver, hvor meget eksekveringstiden vil stige i takt med, at antallet af elementer nændres. Boblesortering er en af de enkleste og mest ineffektive sorteringsalgoritmer. Det kaldes også nogle gange "dum slags". Materiale om dette emne:
En anden sorteringsalgoritme er udvælgelsessortering. Det har også kvadratisk kompleksitet, men mere om det senere. Så ideen er enkel. Ved hvert pas vælger vi det mindste element og flytter det til begyndelsen. Derudover starter hvert pas et skridt til højre. Med andre ord starter det første gennemløb fra det nulte element, det andet gennemløb fra det første osv. Det vil se sådan ud:
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 sortering er ustabil, fordi identiske elementer (med hensyn til hvilken egenskab vi bruger til at sortere elementerne) kan ændre deres relative positioner. Der er et godt eksempel i Wikipedia-artiklen om udvælgelsessortering . Materiale om dette emne:
Indsættelsessortering har også kvadratisk kompleksitet, da vi igen har en loop i en loop. Hvad gør indsættelsessortering anderledes? Denne sorteringsalgoritme er "stabil". Det betyder, at identiske elementer ikke ændrer deres relative rækkefølge. Igen mener vi identiske med hensyn til de egenskaber, vi sorterer 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 sortering
Der er en anden simpel sorteringsalgoritme: shuttle sortering. Dette er også kendt som en tovejs boble sortering eller cocktail shaker sortering. Disse alternative navne fortæller os, at rumfærgen ikke handler om rumfærgen. Det handler om noget, der bevæger sig frem og tilbage. Nu kan du tænke på det, når du tænker på denne algoritme. Hvad er essensen af algoritmen? Essensen af algoritmen er, at vi itererer fra venstre mod højre, bytter elementer og kontrollerer, om nogen af de elementer, der er tilbage i den anden retning, skal 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 anden simpel sorteringsalgoritme er skalsortering. Kernen i det ligner boblesortering, men i hver iteration har vi et andet hul mellem de sammenlignede elementer. Den skæres i to ved hver iteration. 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));
Ud over disse simple sorteringsalgoritmer findes der også mere komplicerede sorteringsalgoritmer. For eksempel flette sortering. Der er to ting at bemærke. For det første kommer rekursion os til undsætning her. For det andet er algoritmens kompleksitet ikke længere kvadratisk, som vi er vant til. Denne algoritmes kompleksitet er logaritmisk. Dette er skrevet som O(n log n). Så lad os implementere det. Først vil vi skrive et rekursivt kald 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);
}
}
Lad os nu tilføje hovedhandlingen til vores implementering. Her er vores super metode:
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øre vores eksempel ved at ringemergeSort(array, 0, array.length-1). Som du kan se, går processen ned til at acceptere et input-array sammen med indikationer af begyndelsen og slutningen af det afsnit, der skal sorteres. Når sorteringen begynder, er disse begyndelsen og slutningen af arrayet. Derefter beregner vi afgrænseren, som er det indeks, hvor vi vil opdele arrayet. Hvis arrayet kan opdeles i 2 dele, så kalder vi sorteringsmetoden rekursivt for de to halvdele af arrayet. Vi forbereder en hjælpebuffer, hvor vi indsætter den sorterede sektion. Indstil derefter indekset i begyndelsen af den sektion, der skal sorteres, og begynd at gå gennem hvert element i den tomme buffer og fyld det med de mindste elementer. Hvis elementet, der peges på af indekset, er mindre end elementet, der peges på af afgrænseren, sætter vi elementet i bufferen og flytter indekset. Ellers, vi placerer det element, som afgrænseren peger på, i bufferen og flytter afgrænseren. Så snart afgrænseren går ud over grænserne for den sektion, der sorteres, eller vi udfylder hele arrayet, betragtes det angivne område som sorteret.Materiale om dette emne:
En anden interessant sorteringsalgoritme er at tælle sortering. Den algoritmiske kompleksitet her er O(n+k), hvor ner antallet af elementer og ker den maksimale værdi af et element. Denne algoritme har en mangel: vi skal kende minimums- og maksimumværdierne i arrayet. Her er et eksempel på optællingssorten:
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 meget ubelejligt, når vi på forhånd skal kende minimums- og maksimumværdierne. Og vi har en anden algoritme her: radix sort. Jeg vil kun præsentere algoritmen her visuelt. Se de supplerende materialer til implementeringen: Materialer:
Nå, det er tid til dessert - hurtig sortering, en af de mest berømte sorteringsalgoritmer. Det har logaritmisk kompleksitet: O(n log n). Denne sorteringsalgoritme er udviklet af Tony Hoare. Interessant nok opfandt han det, mens han boede i Sovjetunionen, hvor han studerede maskinoversættelse ved Moskva Universitet og udviklede en russisk-engelsk parlør. Hvad mere er, bruger Java en mere kompleks version af denne algoritme i Arrays.sort. Hvad med Collections.sort? Hvorfor ikke tage et kig på, hvordan tingene er sorteret "under motorhjelmen"? 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);
}
}
Det hele er meget skræmmende ting, så lad os grave i det. Til input-array ( int[]kilde) opretter vi to markører: venstre ( L) og højre ( R). Under det første metodekald svarer de til begyndelsen og slutningen af arrayet. Derefter identificerer vi pivot-elementet, som er passende navngivet pivot. Herefter er vores opgave at flytte værdier mindre end pivottil venstre for pivot, og større - til højre. For at gøre dette flytter vi først markøren, Lindtil vi finder en værdi større end pivot. Hvis der ikke findes en mindre værdi, så
L bliver lig med
pivot. Så flytter vi
Rmarkøren, indtil vi finder en værdi, der er mindre end
pivot. Hvis der ikke findes en større værdi,
Rbliver den lig med
pivot. Dernæst, hvis
Lmarkøren er før
Rmarkøren eller falder sammen med den, så forsøger vi at bytte elementerne, hvis elementet
Ler mindre end
Relementet. Derefter skifter vi
Ltil højre med 1, og vi skifter
Rtil venstre med 1. Når
Lmarkøren bevæger sig ud over
Rmarkøren, betyder det, at byttet er fuldført: mindre værdier er til venstre for
pivot, større værdier er til højre for
pivot. Herefter kalder vi den samme sorteringsmetode rekursivt på subarrays - fra begyndelsen af den sektion, der skal sorteres, til den højre markør, og fra den venstre markør til slutningen af den sektion, der skal sorteres. Hvorfor fra begyndelsen til højre markør? For i slutningen af en iteration viser det sig, at den højre markør bevæger sig nok til at blive grænsen for den venstre del. Denne algoritme er mere kompleks end simpel sortering, så det er bedst at skitsere den. Tag et hvidt ark papir og skriv: 4 2 6 7 3. Skriv derefter
pivotpå midten, altså under nummer 6. Sæt en cirkel om. Under 4, skriv
L, og under 3, skriv
R. 4 mindre end 6, 2 mindre end 6. Vi ender med at flytte
Ltil
pivotstillingen, for
Lkan ikke bevæge os forbi
pivot, ifølge betingelsen. Skriv igen 4 2 6 7 3. Sæt en cirkel rundt om 6 (
pivot) og sæt
Lden under. Flyt nu
Rmarkøren. 3 er mindre end 6, så sæt markøren
Rpå 3. Da 3 er mindre end 6 (
pivot), udfører vi en
swap. Skriv resultatet: 4 2 3 7 6. Cirkel 6, fordi det stadig er
pivot. Mærket
Ler på 3.
RMærket er på 6. Husk at vi flytter mærkerne, indtil
Ldet går ud over
R. Flyt
Ltil næste nummer. Her vil jeg gerne undersøge to muligheder: 1) tilfældet hvor det næstsidste tal er 7 og 2) tilfældet hvor det er 1, ikke 7.
Hvis næstsidste tal er 1: Flyt
Lmarkøren til 1, for vi kan flytte
Lså længe
Lmarkør peger på et tal mindre end
pivot. Men vi kan ikke flytte
Rfra 6, for vi kan kun flytte R, hvis markøren
Rpeger på et tal, der er større end
pivot. Vi udfører ikke et
swap, fordi 1 er mindre end 6. Skriv den aktuelle situation: 4 2 3 1 6. Cirkel 6 (
pivot).
Lskifter forbi
pivotog holder op med at bevæge sig.
Rbevæger sig ikke. Vi foretager ikke et bytte. Skift
Log
Rmed én position. Skriv
Rmarkøren under 1.
LMarkøren er uden for grænserne. Fordi
Ler uden for rammerne, gør vi ingenting. Men vi skriver 4 2 3 1 igen, fordi dette er vores venstre side, som er mindre end
pivot(6). Vælg den nye
pivotog start alt igen :)
Hvis næstsidste tal er 7:Flyt
Lmarkøren til 7. Vi kan ikke flytte den højre markør, fordi den allerede peger på pivoten. 7 er større end
pivot, så vi udfører en
swap. Skriv resultatet: 4 2 3 6 7. Cirkel 6, fordi det er
pivot. Markøren
Ler nu flyttet til 7, og
Rmarkøren flyttes til 3. Det giver ikke mening at sortere delen fra
Ltil ende, for der er kun 1 element. Vi sender dog delen fra 4 til markøren
Rtil sortering. Vi vælger a
pivotog starter forfra :) Umiddelbart kan det se ud til, at hvis man tilføjer en masse værdier svarende til
pivot, så vil du bryde algoritmen. Men dette er ikke tilfældet. Du kan finde på vanskelige kombinationer og på papiret overbevise dig selv om, at alt er korrekt, og undre dig over, at så enkle handlinger implementerer en så pålidelig sorteringsmekanisme. Den eneste ulempe er, at denne sorteringsalgoritme ikke er stabil. Fordi en swap kan ændre den relative rækkefølge af identiske elementer, hvis et af dem er stødt på før,
pivotfør det andet element er byttet ind i delen før
pivot.
Bundlinjen
Ovenfor så vi på et "gentlemans" sæt af sorteringsalgoritmer implementeret i Java. Algoritmer er generelt nyttige, både fra et anvendt perspektiv og i forhold til at lære at tænke. Nogle er enklere, nogle er mere komplicerede. Smarte mennesker forsvarede deres afhandlinger for nogle. For andre skrev de supertykke bøger. Jeg håber, at de supplerende materialer vil hjælpe dig med at lære endnu mere, da denne artikel blot er en oversigt, der allerede har vist sig at være vægtig. Og dens formål er at give en lille introduktion. Du kan også finde en introduktion til algoritmer, hvis du læser
"Grokking Algorithms ". Jeg kan også godt lide playlisten fra Jack Brown:
AQA Decision 1 1.01 Tracing an Algorithm . For sjov kan du se algoritmevisualiseringer ved
sortering.visualgo.net .
GO TO FULL VERSION