Sortering lister med data presenterer en av de mer utfordrende problemer for programmerere , fordi det er vanskelig å konseptualisere og implementere effektive sortering algoritmer i programmeringsspråk. Sortering krever betydelig kopiering , flytting og lesing av data å jobbe . Følgelig programmerere fokusere på å utvikle effektive og generisk sortering algoritmer . En av disse, flettingen sortere, fungerer ved å dele en liste med verdier over og over rekursivt til " splitt og hersk " problemet . Siden merge slags er ment som en generisk løsning , de fleste språk, inkludert Java , har måter å implementere det. Flett Class
flette sortere tar en liste som skal sorteres og rekursivt deler listen til du kommer til enkeltverdier , for eksempel enkle tall . Den slags recombines da tallene i sortert rekkefølge , til slutt returnere en sortert liste . En grunnleggende sortering klasse i Java vil inneholde en liste til å sortere, og kaller en hoved fusjonere sortering funksjon den definerer : en
klasse Merge {
public int [ ] x ;
public static void main ( String [] args ) {
x = [ 5 , 6, 3 , 4, 7 , 8, 10 , 2 ];
mergeSort ( x , 0 , x . lengde - 1 ) ;
} }
Merge Sorter funksjon
Utenfor den viktigste klassen vil ligge et flettefelt slags funksjon . Denne funksjonen segmenter en rekke tall for å sortere i listen. I første omgang vil dette området representerer hele listen, men som flettingen slags fortsetter, vil det ta bare halvparten av listen inntil nå enkeltposter . Deretter vil flettingen slags funksjon rekombinerer elementene i store lister som er sortert (Kilde 2 ) : en
public void mergeSort ( int lav , int hi ) {
if ( lav < hi ) { int midten = (lav + hi ) /2; mergeSort ( lav, middels ) ; mergeSort ( midten + 1 , hi ), merge ( lav, middels , hi ); } }
Basic Merge funksjon
merge -funksjonen vil kombinere to lister etter å sortere dem . Hvis funksjonen mottar enkeltelementer , vil det bestille dem . Ellers vil det ta to separate lister , og avhengig av ønsket av programmerer for dem i stigende eller synkende rekkefølge :
private void flette ( int lave , int mid , int hi ) {
< p > int [ ] kopi = new int [ x.length - 1 ];
//Kopier begge deler inn hjelperen array for ( int i = lav, i < = hi , i + + ) { kopi [i ] = x [ i] ;}
int i = lav, int j = mid + 1; int k = lav , mens ( i < = midt && j < = hi ) {if ( kopi [ i] < = kopi [ j ] ) { x [ k] = kopi [ i] ; i + +; } else { x [ k] = kopi [ j ]; j + +; } k + +; } //kopier resten på venstre side av tabellen inn i målet rekke while ( i < = mid) { x [ k] = kopi [ i] ; k + +; i + +; }
}
Merge Sorter Recurse
" mergeSort "-funksjonen deler rekursivt listen. Først deles det den opprinnelige listen i to for hver gang det kaller seg rekursivt . Når rekursjon når et enkelt siffer , Backtracks funksjonen da og begynner å bestille listen . Hver gang funksjonen Backtracks til en tidligere funksjon samtale , fusjonerer det to halvdeler av en mindre liste , til slutt jobbe tilbake til den fullstendige listen . "Slå sammen "-funksjonen ser ut til å gjøre de tunge løftene ved å arrangere og kopiering verdier i listen , men hjertet av en sammenslåing slag er i utrolig enkle " mergeSort "-funksjonen .
