Flet sortering i Java
1. Introduktion
I denne vejledning skal vi se på Merge Sort-algoritmen og dens implementering i Java.
Flettsortering er en af de mest effektive sorteringsteknikker, og den er baseret på ”opdele og erobre” paradigmet.
2. Algoritmen
Flettsortering er en "opdele og erobre" -algoritme, hvor vi først opdeler problemet i underproblemer. Når løsningerne til delproblemerne er klar, kombinerer vi dem sammen for at få den endelige løsning på problemet.
Dette er en af algoritmerne, som let kan implementeres ved hjælp af rekursion, da vi håndterer delproblemer snarere end hovedproblemet.
Algoritmen kan beskrives som følgende totrinsproces:
- Opdel: I dette trin opdeler vi input-arrayet i 2 halvdelehvor omdrejningspunktet er midtpunktet i arrayet. Dette trin udføres rekursivt for alle halv arrays, indtil der ikke er flere halv arrays at dele.
- Conquer: I dette trin sorterer vi og fletter de delte arrays fra bund til top og få det sorterede array.
Følgende diagram viser den komplette fusionssorteringsproces for et eksempel array {10, 6, 8, 5, 7, 3, 4}.
Hvis vi ser nærmere på diagrammet, kan vi se, at arrayet er rekursivt opdelt i to halvdele, indtil størrelsen bliver 1. Når størrelsen bliver 1, kommer fletteprocesserne til handling og begynder at flette arrays tilbage under sortering:
3. Implementering
Til gennemførelsen vi skriver en mergeSort funktion, der optager input-arrayet og dets længde som parametre. Dette vil være en rekursiv funktion, så vi har brug for basen og de rekursive betingelser.
Basistilstanden kontrollerer, om matrixlængden er 1, og at den bare vender tilbage. I de øvrige sager udføres det rekursive opkald.
I det rekursive tilfælde får vi det midterste indeks og opretter to midlertidige arrays l [] og r []. Det mergeSort funktion kaldes derefter rekursivt for begge underarrangementer:
public static void mergeSort (int [] a, int n) {if (n <2) {return; } int midt = n / 2; int [] l = ny int [mid]; int [] r = ny int [n - midt]; for (int i = 0; i <mid; i ++) {l [i] = a [i]; } for (int i = mid; i <n; i ++) {r [i - mid] = a [i]; } mergeSort (l, mid); mergeSort (r, n - mid); fusionere (a, l, r, mid, n - mid); }Vi kalder derefter fusionere funktion, der optager input og både underarrays og start- og slutindeks for begge underarrays.
Det fusionere funktion sammenligner elementerne i begge underarrays en efter en og placerer det mindre element i input-arrayet.
Når vi når slutningen af en af underarrayerne, kopieres resten af elementerne fra det andet array til input-arrayet, hvorved vi får det endelige sorterede array:
offentlig statisk tomrumsfletning (int [] a, int [] l, int [] r, int venstre, int højre) {int i = 0, j = 0, k = 0; mens (i <venstre && j <højre) {hvis (l [i] <= r [j]) {a [k ++] = l [i ++]; } andet {a [k ++] = r [j ++]; }} mens (i <venstre) {a [k ++] = l [i ++]; } mens (j <højre) {a [k ++] = r [j ++]; }} Enhedstesten til programmet:
@Test offentlig ugyldig positiveTest () {int [] faktisk = {5, 1, 6, 2, 3, 4}; int [] forventet = {1, 2, 3, 4, 5, 6}; MergeSort.mergeSort (faktisk, faktisk.længde); assertArrayEquals (forventet, faktisk); }4. Kompleksitet
Da flettsortering er en rekursiv algoritme, kan tidskompleksiteten udtrykkes som følgende rekursive relation:
T (n) = 2T (n / 2) + O (n)2T (n / 2) svarer til den tid, det tager at sortere underarrangementer og På) tid til at flette hele arrayet.
Når det er løst, tidskompleksiteten vil komme til O (nLogn).
Dette gælder i værste, gennemsnitlige og bedste tilfælde, da det altid opdeler arrayet i to og derefter flettes.
Rummets kompleksitet af algoritmen er På) når vi opretter midlertidige arrays i hvert rekursivt opkald.
5. Konklusion
I denne hurtige vejledning så vi, hvordan flettsorteringsalgoritmen fungerer, og hvordan vi kan implementere den i Java.
Hele arbejdskoden er tilgængelig på GitHub.
